Back to Catalog
Big O
Avoid in Prod
O(n²) - Quadratic Time
Two nested loops over the same data — fine for n<1000, catastrophic at scale.
Intent & Description
Real-world Use Case
Naive duplicate check: for each element, scan the rest of the array — O(n²). The fix: insert everything into a Set in one pass — O(n). Same result, 1000x faster at n=1000.
Source
📌 TL;DR
O(n²) = nested loops. Works for small n, explodes at scale. Almost always replaceable with O(n) hash map or O(n log n) sort. If you see two nested loops over the same data, ask if there is a better way.
Advantages
- Simple to write — nested loops are intuitive and readable
- Correct by construction — no clever tricks to get wrong
- Perfectly fine for n < ~1000 items where performance is irrelevant
- Useful for learning — understanding why O(n²) is slow teaches algorithmic thinking
Disadvantages
- Degrades catastrophically with scale — n=100k means 10 billion operations
- Almost always has an O(n log n) or O(n) alternative that is worth using
- The most common cause of production performance incidents on growing datasets
- Easy to miss in code review — the inner loop may be hidden inside a called function
Implementation Example
// ❌ O(n²) — Naive duplicate check (avoid for large arrays)
function hasDuplicatesSlow(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) { // Inner loop — O(n²)
if (arr[i] === arr[j]) return true;
}
}
return false;
}
// ✅ O(n) — Hash set approach (same result, linear time)
function hasDuplicatesFast(arr) {
const seen = new Set();
for (const x of arr) {
if (seen.has(x)) return true; // O(1) lookup
seen.add(x);
}
return false;
}
// ❌ O(n²) — Bubble sort (never use in production)
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) { // Nested — O(n²)
if (arr[j] > arr[j + 1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
return arr;
}
// ✅ O(n log n) — Use the built-in (Timsort under the hood)
arr.sort((a, b) => a - b);