Complexity is a contract, not a fact
"O(n)" is not a measurement. It's a contract: a promise about how running time scales <em>given certain assumptions</em>. When those assumptions fail, the contract is void, and fast algorithms become slow ones. This essay names the three assumptions that most often quietly fail in production.
Every complexity statement you have ever read was a contract. "Hash map lookup is O(1)" is a contract with three clauses. "Dynamic array append is O(1) amortised" is a contract with different clauses. "Dijkstra is O((V+E) log V)" has its own. The problem is that most developers read complexity statements as if they were observations about the world, as if the running time were a property of the algorithm alone, rather than a joint property of the algorithm, the input distribution, and the hardware.
I've debugged enough production performance regressions to know what happens when the contract is violated. Nothing looks wrong. The code looks correct. The complexity on paper is fine. But the program is slow. The cause is usually one of three assumption failures, and naming them is worth a thousand profiler sessions.
Assumption 1. The input distribution
Quicksort is O(n log n) in expectation. It is O(n²) in the worst case. The difference depends entirely on the distribution of inputs. Over random inputs, quicksort's partition cuts the array in half on average; over already-sorted inputs with a naive pivot choice, partition cuts off one element at a time and the algorithm degenerates to bubble sort.
Production systems do not see random inputs. They see inputs correlated with yesterday's inputs, with the current hour, with the week of the month. If your data is already nearly sorted, which it almost always is, because most real-world data is derived from some ordering, a naive quicksort is slow. Randomised pivot selection or introsort (the hybrid used in C++'s std::sort) fix this; plain median-of-three pivot selection does not, if the adversary is "every time the user sorted yesterday".
The general pattern: an algorithm's claimed complexity assumes an input distribution. Find out what distribution it assumes. Then check whether your production inputs match.
Assumption 2. The cost of primitive operations
When CLRS writes "each operation costs a constant", it means "a constant with respect to n". It does not mean "a constant with respect to everything". Hashing a string of length L costs O(L), not O(1). Comparing two strings of length L costs O(L). So a hash-map lookup keyed on strings of length L is not O(1), it's O(L). For most applications L is small and constant, and the shorthand works. For applications where L is large or unbounded (URLs, log lines, tokenised search queries) the complexity statement silently lies.
The same failure afflicts Python code that uses arbitrary-precision integers. Python's int has no size limit, so multiplying two n-digit integers is O(n) in bit-length, or rather, O(n²) with schoolbook multiplication, O(n log n) with the Karatsuba-based algorithm Python actually uses. A Fibonacci computation that looks O(n) in iteration count is actually O(n²) in bit operations, because the numbers themselves grow. I have seen Jupyter notebooks that "worked fine up to n = 1000" run for hours at n = 10000, because the asymptotic was wrong in the only way that mattered.
The lesson: every "O(1)" that operates on a non-atomic value is a lie the field tells itself. Size-aware complexity is more honest.
Assumption 3. The memory model
Algorithmic complexity assumes uniform memory: every access costs the same. Real memory is a hierarchy. L1 cache hits are ~1 ns; L2 hits are ~4 ns; main memory hits are ~100 ns; disk is milliseconds. A "linear scan" of a billion-element array that fits in RAM is fast; the same scan of an array that pages to disk is three orders of magnitude slower, and the complexity analysis does not see the difference.
The practical consequence is that contiguous data beats pointer-chasing even when the asymptotic complexity is identical. A linear search over a vector can outperform a binary search over a linked list, because the linear search touches cache lines sequentially while the binary search jumps randomly through memory. Sedgewick's measurements on this are striking: for small-to-medium n, the "asymptotically worse" algorithm wins in wall-clock terms.
This is also why Python's list operations are often faster than the hash-based data structures "should" be in asymptotic terms. The cache effects favour contiguous storage, and the hash table's bucket layout spreads work across unpredictable cache lines. Asymptotic thinking alone will not predict which is faster.
Amortised versus worst-case
A fourth assumption worth naming separately: amortised complexity is an average, not a guarantee. list.append is amortised O(1) in Python, because occasional resizes cost O(n) but are rare enough to be absorbed. In steady-state throughput, this is fine. In real-time systems with hard latency budgets, it is not, one of those amortised resizes might be the one that misses your deadline.
Game engines, trading systems, and audio-processing code commonly refuse amortised data structures. They preallocate at the maximum expected size and reject inserts that would force a resize. The result is worst-case O(1), which is what the deadline actually requires. Most engineers never encounter this constraint, but when it bites, understanding that "amortised" and "worst-case" are different things is the whole game.
How to read complexity statements after reading this
When someone says "X is O(f(n))", ask:
- Over what inputs? Worst case, average case, expected case over a specific distribution?
- Counting what operations? Comparisons, memory accesses, bit operations, hash computations? The choice matters.
- With what memory assumptions? Uniform RAM? Fits in L3? Out-of-core?
- Amortised or worst-case? And, if amortised, can the worst-case single operation hurt you?
Applied to a real example: "Python dict lookup is O(1)" expands to "O(1) amortised expected, over non-adversarial keys, assuming the keys are atomic or have bounded hash cost, with uniform memory access costs, under hash-table load factors that are periodically bounded by resizing". That is the full contract. When you use a dict keyed on long strings in a tight loop inside a real-time system, multiple clauses of that contract are under stress at once.
Practical advice
Three habits make a large difference:
- Name the assumption explicitly when you state a complexity. "O(n) expected, over uniformly distributed keys, with bounded hash cost" is more useful than "O(n)" in a code review, it flags what will go wrong when the assumption fails.
- Profile on production-shaped inputs. Synthetic benchmarks violate assumption 1 almost always. Use real logs, real URLs, real user behaviour.
- Prefer simple cache-friendly code over "asymptotically better" alternatives for small n. The crossover point for "better" is often larger than your n.
The clauses, side by side
The same notation hides different fine print depending on the operation. Read this table as "what the O() is quietly assuming", and notice how often the assumption is about your data rather than about the code.
| Claim | Case it describes | Hidden assumption | How it fails in production |
|---|---|---|---|
| Hash map lookup is O(1) | Expected, amortised | Keys hash near-uniformly and hashing is O(1) | Long string keys, or adversarial keys chosen to collide |
| Dynamic array append is O(1) | Amortised worst case | Occasional O(n) resize is acceptable | A real-time deadline that a single resize blows through |
| Quicksort is O(n log n) | Average over random pivots | Input is not already sorted or adversarial | Nearly sorted input with a naive pivot, degrading to O(n^2) |
| Binary search is O(log n) | Worst case | Random access is uniform cost | Data on disk, where each probe is a seek |
| Linked list insert is O(1) | Worst case | You already hold the node | Finding the node first, which is O(n) |
| Set union-find is near O(1) | Amortised, inverse Ackermann | Path compression and union by rank are both present | One of the two optimisations dropped in a rewrite |
A worked example with real numbers
Consider deduplicating 10 million log lines, each about 200 bytes, keyed by the full line. The hash-set approach is O(n) and the sort-then-scan approach is O(n log n), so the asymptotic verdict is unambiguous. Measure it and the verdict often reverses.
The hash set must compute a hash over 200 bytes per line, which is real work that the O(1) claim treats as a constant, and it stores 10 million pointers scattered across roughly 2 GB of heap, so nearly every lookup is a cache miss costing on the order of 100 nanoseconds. The sort touches the same data in long sequential runs that the prefetcher handles well, and log2(10^7) is about 23, so the extra factor is 23 rather than something frightening. On a machine where a cache miss costs 100 times a sequential access, an algorithm doing 10^7 random probes can lose to one doing 2.3 x 10^8 sequential comparisons. The asymptotics were never wrong; the unit of work they were counting simply was not the unit the machine charges for.
The lesson is not that complexity analysis is useless. It is that O(n) versus O(n log n) is a statement about how the cost grows, and at a fixed n of 10 million, growth is not what you are paying for. Ask which operations dominate, then measure.
Closing thought
Complexity notation is one of the greatest intellectual achievements in computer science. It lets us reason about algorithms without knowing anything about the machine they'll run on. That abstraction is the source of its power and, in production, of its hazards. Use it as a contract, not as a promise. Read the clauses.
Frequently asked questions
If the constants matter so much, why teach asymptotic complexity at all?
Because it is the only part of the analysis that survives a change of machine, language or compiler. Constants are measured; growth rates are reasoned about. You need both, and only one of them can be worked out on a whiteboard before the code exists.
When is amortised O(1) not good enough?
When a single slow operation is itself the failure. Real-time audio, control loops and anything with a per-request latency budget care about the worst individual operation, not the average over a million of them. In those settings, prefer a structure with a bounded worst case even when its average is worse.
How do I know which assumption is being violated?
Profile on production-shaped input and compare the measured curve against the predicted one. If doubling n more than doubles the time for an O(n) algorithm, something in the contract has broken, usually cache behaviour, hash quality or an input that was quietly adversarial.
If you want the mechanics of amortised analysis in detail, the relevant section on dynamic arrays covers the doubling-strategy proof, and the hash-maps module discusses amortised O(1) operations and when they degrade.