Big-O Without the Maths: a Prediction, Not a Measurement
Your function ran in 40 milliseconds on your laptop. That number tells you almost nothing, because a stopwatch measures the trip you just took and Big-O predicts the road you are on. Here is what Big-O actually counts — growth, not time — taught with one Python function, real measured numbers, the hidden linear scan that turns 258 ms into 0.9 ms with one word, and the honest half nobody writes down: the crossover below which the worse complexity class wins on the clock, every time.
You ran the function. It took 40 milliseconds. You shipped it.
Here is the same function, on the same laptop, with nothing changed but the size of the list handed to it:
| orders in the list | wall clock |
|---|---|
| 10 | 4.7 µs |
| 1,000 | 37.8 ms |
| 8,000 | 2.4 s — the page times out |
Eight times the data. Sixty-four times the wait. Nobody touched the code, nobody touched the machine.
That is the entire subject, and it explains why the 40 ms told you nothing. A stopwatch tells you what one trip cost today. It cannot tell you which road you are on. Big-O is the road.
Big-O is a prediction about a graph you have not plotted yet — how the cost grows when the input grows. It is not a measurement, it is not a speed, and it will not make today faster.
Everything below was executed, not quoted: an Intel i5-9400F on CPython 3.10.12, every timing the minimum of five to nine repeated batches because a busy box lies in the mean.
The running example
One function, one list, all the way down. Orders come in as dicts; the risk team sends a list of flagged customer ids every morning; the job is to say which orders belong to a flagged customer.
# one order is one dict. orders is a plain Python list of them.
orders = [
{"id": 8801, "customer_id": 412, "amount": 39.90},
{"id": 8802, "customer_id": 907, "amount": 12.00},
# ... 8,000 on a normal Friday, 20,000 on a busy one
]
# ids the risk team sends over every morning
flagged = [412, 55, 9013, 7788] # about 2,000 of these
# the job: which orders belong to a flagged customer?
Nothing exotic. That is the point — the expensive mistakes in this article all live in code that passes review.
What Big-O throws away, and why that is the feature
Big-O keeps the shape of the growth and discards everything else: the constant factors, the lower-order terms, your CPU, your Python version, whether the list was warm in cache. 3n² + 500n + 9000 becomes O(n²).
That sounds like vandalism. It is what makes the number portable: it survives a faster laptop, a different language, and next year's hardware, because doubling the input still quadruples the work no matter what machine you run it on.
And the limitation is the same sentence read backwards, which is why you should say both in one breath: it threw away exactly the numbers that decide whether today is fast. We come back to that in the honest half.
The three questions that decide your complexity class
"This function is O(n)" is not a property of the function. It is the answer to three questions you have to ask first.
1. Which operation are you counting?
# three functions. same list. same n. wildly different promises.
def total(orders):
return sum(o["amount"] for o in orders) # n additions
def newest_first(orders):
return sorted(orders, key=lambda o: o["id"]) # n log n comparisons
def worst_offender(orders, flagged):
hits = flag_orders(orders, flagged) # n hash lookups
return max(hits) if hits else None # n more comparisons
Same n, three different counted operations, three different classes. "Order n" is meaningless until you say n what, counted how.
2. Worst, average, or amortized?
These are three different promises and they are routinely quoted as if they were one:
| promise | what it claims | measured example |
|---|---|---|
| average | what you get on typical input | dict lookup: 178 ns |
| worst case | what the adversary gets | dict lookup with all 5,000 keys colliding: 179.8 µs — about 1,000× worse, and it doubles as the dict doubles |
| amortized | the average over a long run, where a rare expensive step is paid for by many cheap ones | list.append: 69 ns typical, with roughly 1 in 500 costing 5× as the list grows its backing store |
Amortized is not a weaker version of worst case. It is a promise about the total over many operations — which is exactly the promise you want for append, and exactly the wrong promise if a single slow call blows your p99.
3. What is n, really?
In flag_orders above there are two inputs that grow: the orders, and the flagged ids. Calling either one "n" hides the other. Which brings us to the best beat in the whole topic.
The loop everybody sees
# the slow one everybody can SEE, because the loops are stacked
def duplicate_amounts(orders):
pairs = []
for a in orders: # n times
for b in orders: # n times, for every one of those
if a["id"] != b["id"] and a["amount"] == b["amount"]:
pairs.append((a["id"], b["id"]))
return pairs
Two levels of indentation. 8,000 orders is 64,000,000 trips through that if. Nobody merges this without noticing, and if they do, the doubling test convicts it instantly — the measured ratios as n doubles are 4.075, 4.005, 4.008, 3.997. Dead on 4.0. Double the input, quadruple the work: that is what quadratic is, without a single line of algebra.
For comparison, the same doubling test on a linear pass gives a mean ratio of 2.01, and on a binary search it barely moves at all: from 500 items to 2,000,000 items — four thousand times the data — the search went from 229 ns to 379 ns.
The loop nobody sees
Now count the levels of indentation here. There is one.
# app/risk.py
def flag_orders(orders, flagged):
out = []
for o in orders: # n times
if o["customer_id"] in flagged: # and this line is a loop too
out.append(o["id"])
return out
flagged is a list, so in walks it from the front, for every single order. The second loop is real. It is just not written down. n orders × m flagged ids, in a function that looks linear to every reviewer who has ever looked at it.
Measured, with len(flagged) = n // 10:
| orders | flagged | flagged as a list | as a set | speedup |
|---|---|---|---|---|
| 1,000 | 100 | 0.605 ms | 0.042 ms | 14.5× |
| 5,000 | 500 | 14.24 ms | 0.207 ms | 68.6× |
| 20,000 | 2,000 | 257.9 ms | 0.86 ms | 300.7× |
The speedup grows with n — 14×, then 69×, then 301× — and that growth is the fingerprint. Twenty times the data made the list version 426× slower than its own baseline, which is almost exactly 20². The set version grew 20.5× for 20× the data. One of those is quadratic and one is linear, and you can tell which without reading a single line of theory.
The mechanism is one table. Cost of one membership test for a key that is not there:
| container size | x in list | x in set |
|---|---|---|
| 10 | 63.8 ns | 15.4 ns |
| 100 | 530.2 ns | 15.4 ns |
| 1,000 | 5,095.8 ns | 15.1 ns |
| 10,000 | 50,972.5 ns | 14.3 ns |
| 100,000 | 510,580.9 ns | 13.8 ns |
The list column multiplies by ten every time the size multiplies by ten. The set column is flat — 15.4 ns at ten elements, 13.8 ns at a hundred thousand. That is O(n) against O(1), measured, in one table.
The fix is one word
# app/risk.py
def flag_orders(orders, flagged):
flagged = set(flagged) # built once, up front
out = []
for o in orders:
if o["customer_id"] in flagged: # now: one hash. one step.
out.append(o["id"])
return out
Same loop. Same line. Same letters. The container underneath changed. 20,000 orders: 257.9 ms became 0.9 ms.
No profiler was needed and no clever algorithm was invented. Somebody just asked what in costs on the thing it was given — which is the only skill this whole subject is really teaching.
The honest half
Here is where most Big-O articles stop, and where the interesting part starts. Three claims everybody repeats, checked against a clock.
"At small n it makes no difference" — false as stated
Three implementations of does this batch contain a duplicate id?, at ten orders:
| implementation | µs per call | vs the best |
|---|---|---|
| O(n) — set | 0.938 | — |
| O(n log n) — sort | 1.534 | 1.6× |
| O(n²) — nested loop | 4.700 | 5.0× |
The gap is 3.76 µs against a largest measurement noise of 0.086 µs — 44× the noise. The quadratic version is already 5× slower at ten items, and already ≥2× slower at five. There is no n at which they are indistinguishable as a ratio.
What is actually missing at small n is the consequence, not the ratio:
At ten orders the entire spread between the best and the worst algorithm is 3.8 microseconds. You would have to call it 265,804 times before that choice costs you one second. At 5,000 orders the same three take 0.42 ms, 0.59 ms and 960 ms.
That is the sharper lesson, and it is the one that tells you when to care.
"The better complexity class wins" — only above a crossover
Python's built-in sorted() is O(n log n) but implemented in C with a tiny constant. A hand-rolled counting pass in pure Python is genuinely O(n) with a large one. Which wins?
| orders | sorted() — O(n log n) | pure-Python pass — O(n) | winner |
|---|---|---|---|
| 100 | 8.1 µs | 100.0 µs | sorted(), by 12.4× |
| 1,000 | 137.9 µs | 182.5 µs | sorted(), by 1.3× |
| 1,500 | 215.5 µs | 215.1 µs | dead heat |
| 6,000 | 994.4 µs | 545.6 µs | the O(n) pass, by 1.8× |
| 1,000,000 | 245.6 ms | 130.4 ms | the O(n) pass, by 1.9× |
The crossover is at roughly 1,300–1,500 orders. Below it, the worse complexity class wins on the clock — every time, not occasionally. The C implementation's per-element constant is 10.6× smaller, and that constant buys it the entire region where most code actually lives.
The theory is not wrong. It is a statement about the limit, and your production data may never get there.
"A million items is twenty steps" — confirmed, with one honest correction
Counting real comparisons in a real binary search, exhaustively at small n and over 220,000 random targets at a million:
| n | worst case, measured | average, key present |
|---|---|---|
| 10 | 4 — not 3 | 2.9 |
| 1,000 | 10 | 9.0 |
| 1,000,000 | 20, never 21 | 19.0 |
Twenty is honest. But the tidy "3 / 10 / 20" you have seen on slides is round(log₂ n), and the real comparison count is floor(log₂ n) + 1 — which is 4 at ten items, not 3. It only bites at tiny n, and it is worth saying out loud rather than rounding away, because the habit of checking is the whole point.
The costs Big-O does not describe
A complexity class counts operations. It does not know what an operation costs.
- One network round trip. A localhost HTTP call, measured, is about 0.2 ms keep-alive and 0.4 ms on a fresh TCP connection — and that is the floor, on the same machine, with no real network involved. Inside a single one of those round trips the fast version of
flag_orderschews through roughly 3,000 orders. If your endpoint makes one extra call, no amount of asymptotic elegance in the loop next to it will show up in the graph. - Where the data physically sits. Big-O counts operations; it does not count how far the bytes are from the CPU, which is a large and measurable effect. That story belongs to arrays vs linked lists — granted here in one line, not re-derived.
- The constant you never measured. See the crossover table above. If you have not timed it on your data, at your n, on your box, you have a class, not a number.
The same graph, one layer up: serving models
If you have moved from backend work into LLM serving, this stops being an interview topic and becomes the line item on the invoice — because the two costs that dominate inference are both growth-class arguments, not stopwatch arguments.
Attention is quadratic in context length. Every token attends to every other token, so the work in a forward pass over a prompt grows with the square of the sequence, not with its length. That is the same shape as the nested loop above, and it behaves the same way: doubling the prompt roughly quadruples that part of the work. It is why a 100k-token context is not "ten times a 10k context", why prompt cost dominates on long documents, and why every serving optimisation you have heard of — sliding windows, sparse attention, chunked prefill — is an attempt to bend that exponent down.
The KV cache is an amortization argument. Generating token t would mean re-attending over all t−1 previous tokens from scratch. Cached, each new token attends against stored keys and values instead, which turns the per-token cost from "redo the whole square" into something linear in what came before. The price is memory that grows with context and batch size — which is why serving systems run out of VRAM long before they run out of FLOPs. Same trade as materializing anything: you paid storage to stop recomputing.
And the crossover rule survives intact. Exact nearest-neighbour search over embeddings is a linear scan; an ANN index is sub-linear. But an index has a build cost, a memory cost and a recall cost, and below a few thousand vectors a plain brute-force scan through a contiguous array will beat it on the clock — for exactly the reason sorted() beat the hand-rolled O(n) pass at 100 orders. Reaching for the vector database at 500 documents is the same mistake as reaching for the fancy algorithm at n = 10, with a bigger bill attached.
The lesson transfers cleanly: know the growth class so you can predict the cliff, measure the constants so you know whether you are anywhere near it.
The verdict
| A stopwatch | Big-O | |
|---|---|---|
| What it answers | What did this trip cost today? | What happens when the input grows? |
| What it needs | Real data, real hardware | The shape of the loops |
| What it misses | Tomorrow, and next year's data volume | Constants, cache, the network, today |
| When it lies | When your test data is small | When your real data is small |
| Use it to | Decide if it is fast enough | Decide if it will survive |
You need both, and neither substitutes for the other. The stopwatch is the only thing that can tell you whether today is fine. Big-O is the only thing that can tell you whether the thing that is fine today falls off a cliff at ten times the volume — which is the failure that always arrives on a Friday, in production, with no code change to blame.
So the practical version, with no maths in it at all:
- Name the operation you are counting, and name what
nactually is. Both of them, if there are two. - Look for the loop nobody wrote. Every
in, every lookup, every helper call inside a loop is a cost you have to know. Alistand asetlook identical at the call site and differ by 36,000× at a hundred thousand elements. - Double the input and time it. A ratio near 2 is linear, near 4 is quadratic, near 1 is logarithmic. That single experiment replaces the entire theory, and it works in any language.
- Then measure the constants, because below the crossover the worse class genuinely wins — and if you never plot the graph, you will never know which side of it you are standing on.
Want the long version? The full 16-minute episode walks every one of these numbers on screen — two hand-drawn curves, one counter, no algebra — including the code for all twelve measurement scripts. The 2-minute version is here if you only want the trap.