Big O & Complexity

Two correct programs can disagree by a factor of a million. One sorts a thousand rows in a blink; the other locks the UI for ten seconds on the same input. Same answer, wildly different running time — and the difference is almost always the shape of the loops, not the hardware, the language, or the cleverness of the code inside. Big O is the language we use to compare those shapes without running either program.

Analogy

Think of Big O as a zoom-out. Walk up close to two cars and they look about the same. Zoom out until they're both thirty miles away, and the one doing 60 mph has already pulled far ahead of the one doing 55. Big O asks: "as your input grows very large, which function's running time grows dramatically faster than the other?" Once n is big enough, constants like "goes 5 mph faster" and lower-order terms disappear — only the dominant growth rate matters.

What Big O actually measures

Big O describes an upper bound on growth rate, not a clock time. When we say binary search is O(log n), we don't mean "it takes log n nanoseconds". We mean: the number of steps it performs is bounded by a constant multiple of log₂(n) once n is large enough. Formally: T(n) = O(f(n)) if there exist constants c and n₀ such that T(n) ≤ c·f(n) for all n ≥ n₀.

Three consequences that trip people up:

• Big O is about growth, not absolute speed. An O(n) algorithm can be slower than an O(n²) algorithm at small n — the constants and lower-order terms dominate until n is big.
• Big O drops constants and lower-order terms. T(n) = 3n² + 17n + 42 is O(n²). Not O(3n² + 17n + 42). Not O(n² + n). Just O(n²).
• Worst case is the default reading. Unless otherwise specified, Big O means worst-case complexity — the pessimistic upper bound. We'll distinguish best / average / worst below.

The six classes you need

Six growth rates cover 95% of everyday code:

Class	Name	Doubling input means	Example
O(1)	constant	work doesn't change	arr[0], hashmap lookup (average)
O(log n)	logarithmic	work goes up by a constant	binary search, balanced-BST probe
O(n)	linear	work doubles	sum an array, find the max
O(n log n)	linearithmic	work slightly more than doubles	mergesort, heapsort, good quicksort
O(n²)	quadratic	work quadruples	nested loops over the same array, bubble sort
O(2ⁿ)	exponential	work squares (!)	naive recursive fib, subset enumeration

At n = 1,000,000, those classes are: 1, 20, one million, twenty million, one trillion, and "the heat death of the universe." The gaps are enormous. Picking the wrong class means your code either works or it doesn't — not "runs a bit slower".

How to read a function and classify it

Stop trying to memorise algorithms. Look at the shape of the control flow:

• No loop, no recursion, no non-constant call → O(1). Indexing an array, arithmetic, object property access. If the body does a fixed number of things, it's constant time.
• One loop from 0..n → O(n). for (i = 0; i < arr.length; i++), for x of arr, .forEach, .map. The work scales with input length.
• One loop whose counter halves each step → O(log n). while (n > 0) n >>= 1;, binary search's window update lo = mid + 1 / hi = mid - 1, tree-walk that always descends the taller side.
• Two nested loops, each over n → O(n²). Classic bubble-sort shape. Watch out for hidden nesting: arr.includes(x) inside a loop over arr is secretly O(n²).
• Outer linear loop wrapping a halving inner loop → O(n log n). Mergesort works this way (log n levels × O(n) work per level). Sorting a collection is almost always O(n log n) with standard library algorithms.
• Recursion that makes two self-calls per invocation → O(2ⁿ). fib(n-1) + fib(n-2). Each level doubles the tree; 2ⁿ nodes total. Memoisation collapses it to O(n).

When in doubt: count the loops and check whether the counter grows or shrinks proportionally. Multiply nested loops. Multiply recursion branching factor by depth.

Dropping constants — with care

O(2n) = O(n). O(100n) = O(n). O(n² + n + 1000) = O(n²). The formal reason is the definition above: any constant factor can be absorbed by c, and lower-order terms are dominated by the leading one for large n.

In practice, constants do matter when you're picking between two implementations in the same class. Quicksort and mergesort are both O(n log n), but quicksort's constants are smaller, so it's usually faster in practice — at the cost of a worse worst case. "Big O equivalent" doesn't mean "identical performance"; it means "same growth rate as n gets large."

Best vs average vs worst

One function can have different complexities depending on which input you feed it:

• Best case. The luckiest input. Bubble sort on already-sorted input is O(n) — one pass, no swaps, early exit.
• Average case. Typical random input. Quicksort with a random pivot: O(n log n).
• Worst case. The adversarial input. Quicksort with always-worst pivot on already-sorted input: O(n²). Hashmap lookups when every key hashes to the same bucket: O(n) instead of O(1).

Unless the spec says otherwise, "the complexity is X" means worst case. Production code that accepts untrusted input must reason about worst case; benchmark numbers usually report average.

Hidden gotchas

A few surprises that bite real code:

• Amortised O(1) isn't worst-case O(1). Pushing to a dynamic array (JS Array.push, Python list.append) is O(1) on average — but every so often the array doubles its capacity and the push is O(n). Averaged across many pushes, that still amortises to O(1) per op.
• String concatenation in a loop can be O(n²). result = result + piece in Java / older Python creates a brand-new string each time, copying every character. Use a builder (''.join(parts), StringBuilder) for O(n).
• Array.includes / Array.indexOf inside a loop is O(n²). Swap the array for a Set to make membership O(1) average.
• Sorting is never free. "Sort first, then binary search" adds an O(n log n) up-front cost. For a single lookup that's worse than a linear scan. It's only a win when you'll re-search many times.
• Recursion with memoisation changes the class. fib is O(2ⁿ) naive; with a memo it's O(n). The recursion structure looks identical — the difference is whether each subproblem is solved once or exponentially many times.

Playground

The Complexity Picker panel shows one stereotyped function at a time and asks you to classify it. Six buttons, one answer per function, running score at the top. Every sample is a canonical shape from this lesson — the body is small enough to read in five seconds, and the explanation after each pick reinforces why the class is what it is. Cycle through all twelve samples and you'll have touched every class multiple times.

Visualizer

The Complexity Curves panel plots O(log n), O(n), O(n log n), and O(n²) on the same axes. At n = 10 they look indistinguishable — the reason small-input benchmarks are misleading. Slide n to 100, to 1000, to 10,000 and watch the quadratic curve rocket off the chart while the log curve barely moves. That visual gap is the lesson: you're not optimising for "a bit faster", you're choosing whether your program still works at production scale.