Big-O Notation Explained with Real Code (Not Just Theory)

Big-O notation is one of those topics that sounds intimidating in a textbook and obvious once you have stared at enough code. The whole idea is to describe how the running time of an algorithm grows as the input gets larger, ignoring constants and small terms because they stop mattering at scale.

If your function takes one millisecond on 10 items but five seconds on 10,000 items, Big-O is what tells you whether that growth is acceptable or about to ruin a production server.

The five complexity classes you actually see

• O(1) — constant time. The work does not grow with the input. Looking up a hash map key, returning a precomputed value.
• O(log n) — logarithmic. Each step throws away half the input. Binary search, balanced tree lookup.
• O(n) — linear. You touch every element once. A single for-loop over an array.
• O(n log n) — linearithmic. You divide the input recursively and do linear work at each level. Merge sort, heap sort, most fast sorts.
• O(n²) — quadratic. A loop inside a loop where both run over the input. Naive sorts, comparing every pair.

How to read complexity off code

Forget formal proofs for a minute. Here is the lazy method that works for 90% of code: count the loops and what they iterate over.

O(1) — constant

function getFirst(arr) { return arr[0]; } — no loops, no recursion, no growth. Always one operation.

O(n) — linear

function sum(arr) { let total = 0; for (const x of arr) total += x; return total; } — one loop, runs once per element.

O(n²) — quadratic

function hasDuplicate(arr) { for (let i = 0; i < arr.length; i++) for (let j = i + 1; j < arr.length; j++) if (arr[i] === arr[j]) return true; return false; } — nested loops, both go up to n. With 10,000 items you do 50 million comparisons. With 100,000 items, five billion. This is the function that kills your server.

O(log n) — logarithmic

Binary search on a sorted array. You look at the middle element, discard half, look at the middle of what remains, discard half again. With a million items you only do about 20 comparisons. The recurrence T(n) = T(n/2) + O(1) gives O(log n).

O(n log n) — fast sorting

Merge sort splits the array in half (log n levels of splitting), then merges the halves at each level (linear work per level). Total: n log n. Quick sort hits the same complexity on average. This is why JavaScript's Array.prototype.sort, Python's sorted, and Java's Collections.sort are all O(n log n).

Why constants do not matter (until they do)

Big-O drops constants: O(2n) is the same as O(n), and O(100n) is the same as O(n). For asymptotic analysis that is correct — eventually n grows faster than any constant. But in real systems, a 100x constant does matter, especially if the input is bounded. Knowing both the asymptotic class and the practical constant is the difference between a correct answer in an interview and a working system in production.

Recognizing slow code in practice

• Two nested loops over the same collection → O(n²). Always ask whether a hash set or sorted array could collapse one of them.
• .indexOf() or .includes() inside a loop → also O(n²) because indexOf is itself O(n). Use a Set.
• Sorting inside a loop → O(n² log n). Sort once outside.
• Recursion that calls itself twice on the same size → exponential. Cache results (memoization) or rewrite iteratively.

A concrete optimization

Naive duplicate detection is O(n²). Replacing the inner loop with a Set lookup makes it O(n): function hasDuplicate(arr) { const seen = new Set(); for (const x of arr) { if (seen.has(x)) return true; seen.add(x); } return false; } — same answer, dramatically faster on large input.

If you paste a function into Solvequill, the explanation video walks through the loops, names the complexity class on screen, and shows where the bottleneck is. It is a fast way to build the intuition without grinding through theoretical proofs.