Big-O without the ceremony

You can recite the classes — O(1), O(log n), O(n log n) — and still stand in front of two working options unsure which one to pick, because knowing the label is not the same as knowing what it promises. Big-O is a claim about growth: how the cost changes as the input gets larger, not how large the cost is for the input actually sitting in front of you. That distinction is the whole article.

What the notation throws away#

Big-O bounds a function from above: a function f is O(g) if, past some starting point, f never exceeds g scaled by some constant. Formally, f(n) is O(g(n)) when there exist constants c and n₀ such that f(n) ≤ c · g(n) for every n at least n₀. Two things follow directly from that shape, and both get lost in casual use. It is a bound, not an estimate — the definition only requires f to stay under the ceiling, not to track it closely. And it holds only “eventually,” past n₀ — a claim about behaviour once the input is large enough, not a claim about the size you actually have.

The freedom to pick any constant c and any threshold n₀ is exactly what lets the notation ignore the things that make two implementations of the same algorithm behave differently in practice. A constant factor is invisible to it by construction: two algorithms that are both O(n) can differ by a large multiplier — one doing three times the work of the other on every input — and the notation records them as identical, because the definition only requires some constant to exist, not that it be small. Lower-order terms vanish the same way: an algorithm that does n² + 1000n operations is O(n²), full stop, even though the 1000n term is the larger of the two for every input under a thousand. And the cost of a single operation was never part of the count — the notation counts operations, not what each one costs to run. An O(1) operation that reaches out to disk can lose badly to an O(log n) operation that never leaves memory, because Big-O was never measuring wall-clock time in the first place.

The useful reframing follows from all three: read Big-O as a description of shape, not a speed rating. Big-O tells you how the cost changes, not what it is. Two algorithms can share a shape and have wildly different real costs, or have different shapes and near-identical costs at the sizes a program actually runs — both are consistent with what the notation promises, because the notation was never promising the second thing.

The table, and when to stop trusting it#

The usual reference is a short table of growth classes, so here it is: five that come up constantly, ordered from cheapest to most expensive, with what each one feels like as the input keeps growing rather than the algebra alone.

Read top to bottom, the table is a ranking: for large enough input, every row beats every row below it, and nothing below it ever beats it back. That ranking is real — it is exactly what the definition in the previous section guarantees, once the input is far enough past whichever n₀ makes the bound apply. What the ranking does not tell you is where “far enough” actually sits for the two specific implementations in front of you, and that gap is exactly where the constants the notation discarded live.

Two classes cross over. Picture a quadratic algorithm with a small constant factor set against a linearithmic one with a larger constant: at small input sizes the quadratic algorithm can be doing less total work, purely because each of its steps is cheaper, and it keeps winning until the input grows large enough that its faster-growing shape outpaces the constant-factor advantage the cheaper steps bought it. Past that crossover the ranking in the table reasserts itself and never lets go again — but “past that point” is doing real work in that sentence, and where the point sits depends on the constants the notation discarded, not on the exponent it kept.

This is not hypothetical. CPython’s own sort documents exactly this trade. Its Timsort implementation works by finding runs already in order and merging them, and when a natural run comes up shorter than the minimum run length the implementation works with, the main loop — in that implementation’s own description — artificially boosts the run to the minimum, using a stable binary insertion sort on the array elements that follow it. The extended run then goes into the merge path like any other. The method doing the extending has the worse growth class of the two and is used here anyway, because across a handful of elements its cheaper steps win outright. The reason for extending at all is a separate one, and it is the reason the implementation states: merges go best when the runs meeting each other are of comparable length, and letting very short natural runs through unchanged would leave that unbalanced. Where the minimum sits is that implementation’s own choice, tuned to its own costs; it is a fact about CPython’s sort, not a universal fact about sorting.

The site’s own sorting visualiser makes a version of this checkable rather than asserted: it counts every comparison insertion sort and merge sort make on the same ten values, one step at a time, and holds two fixed orderings — nearly sorted and reversed — against each other so you can watch which algorithm wins change with the order alone, not the size. A complexity class describes a limit; the visualiser lets you watch one specific run instead of taking the limit’s word for it. That crossover is the kind of thing the site’s foundations pillar exists to work through directly — the material most people meet first, past the point where the standard explanation usually stops.

The rewrite that got slower#

The failure has a recognisable shape: a data structure with better asymptotic behaviour replaces one with worse, on the strength of the complexity classes alone, and the program gets slower. The mechanism is almost always the one already covered — the replacement’s constant factor is larger, and the input the program actually runs on never gets big enough for the crossover to have happened yet. A lookup nominally upgraded from O(n) to O(log n) can end up doing more real work per call than the thing it replaced, because “more work per call, done fewer times” was never guaranteed to net out in the replacement’s favour below the crossover point.

The pattern has two halves: the improvement is invisible in production, and it only shows up once someone benchmarks with an input several orders of magnitude larger than what the program ever actually sees. That gap between the benchmark’s input and the production input is the whole story — the benchmark is honest about what the asymptotics eventually deliver, and the production numbers are honest about the fact that “eventually” has not arrived yet.

None of this makes the notation wrong or the analysis useless. Asymptotics decide which algorithm survives as an input keeps growing, and a program whose input does grow without bound needs exactly that guarantee. The mistake is not running the analysis — it is treating a statement about a limit as though it were a statement about today’s input, without first checking which one the decision actually needs.