10 time-complexity patterns — the Big-O you can watch run
Almost every Big-O you will ever assign comes from recognising one of about ten
shapes in the code. This is a single-file, in-browser poster of all ten — from
the hash lookup that ignores n entirely to the permutation search that dies at
n = 13 — with every row animating at once. It starts running on its own: ten
patterns, ten sweeps, side by side, so you compare shapes instead of clicking
between them.
Nothing on screen is a stand-in number. Each row is expanded into its actual
operation sequence for the current n, and its counter is the length of that
walk. When the triangular loop reports 120 operations at n = 16, that is 120
animated cell visits, and 16·15/2 is printed next to it as a check.
The ten patterns
| # | Pattern | The shape in the code | Big-O | Exact count |
|---|---|---|---|---|
| 1 | Hash lookup | map.get(key) | O(1) | 2, for every n |
| 2 | Halving loop | while (n > 1) n = n / 2 | O(log n) | ⌊log₂ n⌋ |
| 3 | Single loop | for i in 0…n | O(n) | n |
| 4 | Sequential loops | one loop after another | O(n + m) | n + m |
| 5 | Loop + binary search | linear loop, logarithmic body | O(n log n) | n · ⌈log₂(n+1)⌉ probes |
| 6 | Divide & conquer | T(n) = 2·T(n/2) + n | O(n log n) | n · (log₂ n + 1) |
| 7 | Nested loop | loop inside a loop | O(n²) | n² |
| 8 | Triangular loop | inner bound is i, not n | O(n²) | n(n−1)/2 |
| 9 | Branching recursion | two recursive calls per call | O(2ⁿ) | 2·fib(n+1) − 1 calls |
| 10 | Permutations | try every ordering | O(n!) | n! orderings |
Two rules do most of the work
Nearly all of the confusion about Big-O comes down to two questions you can answer by reading the indentation.
Sequential loops add; nested loops multiply. Patterns 4 and 7 contain the
same two loops. Side by side they cost n + m; one inside the other they cost
n × m. At n = 100, m = 60 that is 160 operations versus 6 000 — and the gap
is a ratio, so it widens forever as the inputs grow.
Halving gives you a logarithm. If each step throws away a constant fraction
of what is left, the number of steps is how many times you can halve n before
you reach 1: ⌊log₂ n⌋. A million elements is 19 steps, a billion is 29. This
is why doubling your data is nearly free for a balanced tree or a binary search,
and why pattern 5’s inner search costs 5 probes instead of 16 at n = 16.
Everything else is bookkeeping on top of those two facts. O(n log n) is a
linear loop with a logarithmic body (pattern 5) or a linear amount of work
repeated once per level of a log n-deep recursion (pattern 6). O(n²) is a
loop inside a loop, whether you visit the whole grid or just the half below the
diagonal.
Constants are dropped, and that is the point
Patterns 7 and 8 are the same class. The triangular loop visits
n(n−1)/2 pairs — exactly half of the nested loop’s n² — and Big-O calls both
O(n²), because a constant factor of ½ does not change the shape of the curve.
Halving the constant makes the code twice as fast; it does not make it scale
better. At n = 100 000 the full grid is 10 billion visits and the triangle is
5 billion: both are minutes of CPU where a sort would have taken a second.
The same reasoning is why pattern 1 counts two operations, not one, and is
still O(1). Constant means bounded independently of n — not literally one
instruction.
Where the classes actually break
The last column of every row is the practical version of the whole subject. At a
generous 10⁹ simple operations per second, here is the biggest n each class
still finishes inside one second:
| Class | Largest n in 1 s | What that feels like |
|---|---|---|
O(1) | any n | never the bottleneck |
O(log n) | any n | a trillion elements costs 40 probes |
O(n) | 1 000 000 000 | memory bandwidth limits you before the algorithm does |
O(n log n) | ≈ 39 000 000 | sorting tens of millions of rows |
O(n²) | ≈ 31 600 | fine on a test fixture, fatal on real data |
O(2ⁿ) | ≈ 30 | needs pruning or dynamic programming |
O(n!) | 12 | needs a heuristic, not a faster machine |
The interesting row is O(n²). Thirty thousand items is a plausible size for a
development dataset and an implausible one for production, which is why the
nested loop is the single most common cause of code that works on a laptop and
falls over at scale.
Reading the screen
One page, four columns, ten rows ordered by how fast they grow:
- Pattern — the code that produces the shape, with the line the current operation belongs to lit. Each row lights its own line, so ten different statements are executing at any moment.
- Visualization — the work itself: buckets, cells, two passes, a shrinking search window, merge levels, grids, call trees. Every element answers when you point at it.
- Growth — that class’s curve from
n = 1to32. All ten boxes share one log₁₀ scale, so how high a curve sits ranks it against the other nine; the grey line ghosted behind it isO(n), drawn identically in every box. - Big-O — the class, the exact operation count at the animated
n, and the largest input this class still finishes in one second.
Two pacing modes, and the difference between them is the whole point:
- Unison (default) — every row completes its sweep in the same time, so the ten shapes are directly comparable.
- Real cost (turn Unison off) — every row executes exactly one operation per tick. Twenty ticks in, the hash lookup finished eighteen ticks ago and the linear loop is done, while divide & conquer is a quarter through its 80 operations and the nested loop has 44 cells left. That lag is the Big-O.
Controls: space run/pause · s step · S step ×10 · r reset · ↑ / ↓
move the narration spotlight · 1–9, 0 spotlight a row directly. Hovering
or clicking a row narrates it immediately. The n slider changes the input
size for every row at once.
Rows cap the n they draw so each figure stays legible — a 32×32 grid is 1024
cells, and a 5-deep permutation tree is 326 nodes. The growth curve and the
one-second budget always use the real n, and the hover text says which cap is
in force.
The parts that are more subtle than one line of a table
A one-page summary has to simplify. Four places where the honest answer is longer than the label:
Hash lookup is O(1) on average, not always. Two keys can hash to the same
bucket. With a decent hash function and a load factor kept below ~0.75 the
average chain is short enough to call constant, but a worst case where every key
collides degrades to O(n) — which is why Java’s HashMap converts a bucket to
a red-black tree (O(log n)) past eight entries, and why hash-collision denial
of service was a real class of vulnerability.
Binary search assumes the array is already sorted. Pattern 5 is O(n log n)
only for the searches. Getting the array sorted in the first place is another
n log n — which is exactly pattern 6. The reason the combination still wins is
that you pay the sort once and the searches many times.
Naive fib is not really 2ⁿ. The call count is exactly 2·fib(n+1) − 1, so
it grows like φⁿ with φ ≈ 1.618, not 2ⁿ. O(2ⁿ) is a true upper bound but
a loose one; the sim reports the exact call count next to it, and you can watch
the ratio between consecutive n settle on the golden ratio. Memoising the same
function collapses the tree to one node per distinct argument — O(2ⁿ) becomes
O(n) with a cache and no change to the algorithm.
Big-O says nothing about wall-clock time. It counts operations, and it
throws away every constant — including the ~100× between an L1 cache hit and a
main-memory read. A cache-friendly O(n²) pass over a contiguous array can beat
a pointer-chasing O(n log n) for small inputs. Big-O tells you which one wins
eventually, and the growth plot shows how quickly “eventually” arrives: by
n = 32 the curves are already separated by nine orders of magnitude.