S015 · Big-O Notation — Reasoning About Scale
How to talk about performance without measuring: growth rates, worst/avg/amortised cost, and the constant-factor traps that make theory disagree with reality.
🎯 Look at a snippet of code and, without running it, predict how its runtime and memory will scale — and know when Big-O lies to you in practice.
Why this session exists
Two engineers write code that does the same thing. On 1000 rows, both finish instantly. On 10 million rows, one finishes in 3 seconds and the other times out after 20 minutes. The difference is not the language, the CPU, or the cleverness — it's that one algorithm is O(n) and the other is O(n²). Big-O is the vocabulary that lets you predict this before you write the code, and diagnose it before you profile. Skip this and you'll spend your career surprised by performance. Learn it and you'll pick the right data structure the first time.
- Read a loop and say its Big-O out loud (n, n log n, n², etc.) without hesitation.
- Explain why O(n log n) sort beats O(n²) even though the constant is bigger.
- Distinguish worst-case, average-case, and amortised cost — and give one example of each.
- Explain why a theoretically slower algorithm can win in practice (cache, constants, small n).
- Sketch the shape of every common curve — 1, log n, n, n log n, n², 2ⁿ — on a napkin.
Prerequisites
- S005–S008 — you can read Python loops, list comprehensions, and function calls.
- Basic algebra (exponents, logs). No calculus required.
(a) Intuition · 5 min
Two moving companies quote you. Company A: "we charge per box." Company B: "we charge per box times per box." For 10 boxes, both are cheap. For 10 000 boxes, one quote is 10 000× the other. That multiplication of scale-shape is Big-O.
Big-O is not "how long will this take?" It's "how does the cost grow as the input grows?" A 10-line function running on a laptop can take a millisecond or a millennium depending on the shape.
When we say "this is O(n)", we mean: if input doubles, work roughly doubles. O(n²) means input doubles, work quadruples. O(log n) means input doubles, work goes up by one step. O(1) means work does not depend on input at all.
The tell is always the loop structure. One loop over the input → O(n). A loop inside a loop over the same input → O(n²). Halving the search space each step → O(log n).
The shapes you actually see
- O(1) — constant. Hash-map lookup, array index. Doesn't care how big n is.
- O(log n) — logarithmic. Binary search, balanced tree operations. Halves the problem each step.
- O(n) — linear. Walk once through the input. `sum(xs)`, `max(xs)`, single-pass filter.
- O(n log n) — linearithmic. Efficient comparison sorts (merge, heap, quicksort avg).
- O(n²) — quadratic. Nested loop over the input. Fine for n<10³, disaster for n>10⁵.
- O(2ⁿ) — exponential. Brute-force subset enumeration. Dies past n≈25.
- O(n!) — factorial. Brute-force permutations, travelling salesman. Dies past n≈12.
A quick history
- 1894Bachmann introduces O(…)German mathematician Paul Bachmann uses ‘O’ in a number-theory paper. Landau popularises it.
- 1976Knuth · asymptotic notation for CSDonald Knuth's ACM paper standardises O, Ω, Θ notation for algorithm analysis.
- 1990CLRS textbook · the definitive treatmentIntroduction to Algorithms by Cormen et al. — the book every CS grad has scars from.
- 2010sCache-aware algorithmsPractitioners realise memory hierarchy (L1/L2/L3/RAM/disk) makes ‘Big-O optimal’ not always ‘fastest’.
- 2020sSIMD & GPU · constants that dwarf Big-OFor dense linear algebra, a 100× hardware constant reshuffles which algorithms win in practice.
(b) Visual walkthrough · 15 min
How each shape grows (mentally, on a log-log plot)
How to read a loop in your head
One loop over n items → O(n). Two nested loops over the same n → O(n²). Loop over n inside a loop over m → O(n · m).
`while lo <= hi: mid = (lo+hi)//2` → O(log n). Every iteration halves the search space.
T(n) = 2·T(n/2) + O(n) → merge-sort → O(n log n). Master Theorem gives you the shortcut.
3n² + 100n + 42 → O(n²). Only the fastest-growing term survives.
If you get O(1) for something that walks the list, you dropped a loop. If you get O(n^7), you probably counted a constant loop.
Common data-structure operations (memorise this)
Operations you'll do 10 000 times a year
Worst-case vs average vs amortised
The pessimist's promise
- Guaranteed upper bound on ANY input
- Used for hard real-time systems
- Quicksort worst-case: O(n²) on already-sorted input
- Guides pathological-input decisions
The statistician's estimate
- Expected cost over random inputs
- Assumes an input distribution
- Quicksort average: O(n log n)
- Guides typical-workload decisions
The banker's account
- Expensive operations paid for by many cheap ones
- list.append is O(1) amortised (resize is O(n) but rare)
- Union-Find with path compression: O(α(n)) ≈ O(1)
- Guides throughput analysis
Mental model
"O(n log n) beats O(n²), so the lower-complexity algorithm is the faster one. Big-O tells me which implementation to pick."
Big-O describes the growth rate as n → ∞, with all constants and lower-order terms deliberately discarded. Two algorithms in the same class can differ by orders of magnitude in wall-clock time, and a "worse" class routinely wins below some crossover point — which is why real sort implementations switch to insertion sort for small subarrays.
Because for the large inputs used to teach it, the claim is true, and asymptotics genuinely is the right tool for choosing between a linear scan and a hash lookup at scale. What the notation hides is everything that dominates at realistic sizes: the constant factor, memory access patterns, and the fact that a sequential array scan and a pointer-chase through a linked structure have identical O(n) but wildly different real cost, because one is cache-friendly and the other issues a cache miss per element. The gap between "same complexity" and "same speed" is where most performance work actually lives, and Big-O is structurally incapable of showing it to you.
Same asymptotic class, very different behaviour — measure, don't assume:
import timeit
setup = 'import numpy as np; a = list(range(1_000_000)); b = np.arange(1_000_000)'
print(timeit.timeit('sum(a)', setup, number=10)) # O(n)
print(timeit.timeit('b.sum()', setup, number=10)) # also O(n)
# and the crossover: O(n^2) insertion sort wins on tiny n,
# which is why CPython's Timsort uses it for short runs.Why can no comparison-based sort do better than O(n log n)? This is not "nobody has found one yet" — it is a proof that none can exist. Derive it.
- 1A comparison sort learns about the input only through comparisons, each returning one of two outcomes.forced by · by definition it may not inspect the values themselves, only their relative order
- 2Its execution is therefore a binary decision tree: each internal node is a comparison, each branch an outcome, each leaf a final permutation the algorithm outputs.forced by · the algorithm is deterministic given the comparison results, so the results fully determine the path
- 3The tree must have at least n! leaves, since any of the n! input orderings must be sortable and each needs a distinct output permutation.forced by · two different required permutations reached by the same path would mean one of them is produced wrongly
- 4A binary tree with L leaves has height at least log₂(L), and the height is the worst-case number of comparisons.forced by · each level at most doubles the reachable leaves, so you need log₂(L) levels to reach L of them
- 5So worst-case comparisons ≥ log₂(n!), and by Stirling's approximation log₂(n!) ≈ n log₂ n − n·log₂e, which is Θ(n log n).forced by · n! grows fast enough that its logarithm is dominated by the n log n term
Therefore Θ(n log n) is an information-theoretic floor, not an engineering limitation. No cleverness escapes it while the only tool is comparison.
And note exactly what this predicts — and it's the useful part: the bound applies only to comparison-based sorting. If you can extract information without comparing, the proof doesn't apply, and indeed counting sort and radix sort run in O(n) by using the values as array indices. That is why sorting billions of fixed-width integer keys is done with radix-style passes, not quicksort. The bound also predicts that a sort exploiting existing order can beat it on already-partially-sorted input — which is precisely what Timsort does, hitting O(n) on sorted data.
Ask one question of any piece of code: if the input is 10× bigger, what happens to the time? Unchanged → O(1). 10× → O(n). Slightly more than 10× → O(n log n). 100× → O(n²). That single question, answered honestly, is 90% of the value of complexity analysis and takes five seconds.
Then ask the second question that Big-O silently omits: what does memory do? An algorithm that is 2× faster but holds the whole input in RAM is not faster — it is a different algorithm with a hard ceiling, and it will fail at some input size rather than merely slow down.
- Nested loops over the same data multiply; sequential loops add. A loop containing a linear operation —
inon a list, string concatenation, aDataFrameappend — is quadratic even though it looks linear. - Halving the search space each step is where log n comes from. If you see binary search, a balanced tree, or divide-and-conquer, you have a log factor.
- Worst case is what you design for; average case is what you usually experience; the gap is where production incidents live — hash tables are O(1) average and O(n) worst, and adversarial or skewed keys can find that worst case.
- Constants matter below the crossover, and most real inputs are below someone's crossover. Measure before optimising complexity you only assumed was the bottleneck.
Fire this model the moment you see: a loop inside a loop over the same collection · if x in some_list inside a loop · string built by += in a loop · a job whose runtime quadrupled when the data doubled · a query plan showing a nested-loop join over two large tables.
A job is too slow. Do you improve the algorithm's complexity, tune constants, or throw hardware at it?
Profile first; the bottleneck is regularly not where you assumed. Then fix complexity, then constants, then hardware — in that order, because each later step is cheaper to do and more expensive to keep.
The trap worth naming: scaling out a quadratic algorithm looks like a fix and is a compounding bill. Doubling the cluster buys you a 1.4× increase in tolerable input size, and you will pay for that capacity every day forever. Complexity problems are the only ones where an afternoon of thinking beats an unlimited budget.
(c) Hands-on · 25 min
You'll write four search implementations of the same task ("does list contain x?"), time them, and see the curves for yourself. Save as bigo_demo.py in a fresh venv.
Run it:
uv run python bigo_demo.pyExpected shape of output (numbers vary by machine):
What each block does
Anatomy of the benchmark
Add a third algorithm and predict its shape before measuring:
def three_sum_naive(xs: list[int], target: int) -> bool:
"""O(n³) — do any three elements sum to `target`?"""
n = len(xs)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if xs[i] + xs[j] + xs[k] == target:
return True
return FalsePredict: at n=100 vs n=200, how many times slower? (Answer: (200/100)³ = 8×.) Now benchmark it and see if reality agrees. If it doesn't, ask why — cache effects, branch prediction, or a bug?
(d) Production reality · 15 min
Discord's read-message-status service used a Cassandra cluster. As user counts grew, per-request latency crept up. Profiling showed the hot path was a per-guild scan — O(members × channels) — that had been fine at 1 000 members and was crippling at 250 000.
Symptoms: p99 latency creeping from 20 ms to 800 ms over 6 months. No single deploy caused it. The algorithm had a hidden n term that only became a problem at real scale.
if item in seen: continue; seen.append(item) where seen is a list. For 100 items, instant. For 100 000 items, it takes 45 minutes and the engineer wonders if their laptop is broken.Change seen from a list to a set. Same logic; O(n) instead of O(n²).
# slow: O(n^2) — `in list` is O(n)
seen = []
for item in items:
if item in seen: continue
seen.append(item)
# fast: O(n)
seen = set()
for item in items:
if item in seen: continue
seen.add(item)in list is O(n); in set/dict is O(1). This one substitution has saved more junior-engineer weeks than any other optimisation.Where this shows up in the rest of the plan
(e) Recall + stretch · 10 min
Explain-out-loud test
- What does O(n²) mean in plain language, and what code shape produces it? (one sentence, one code shape)
- Why does binary search require a sorted list, and what's its complexity? (name the two)
- When does Big-O lie in practice, and what should you do about it? (name one situation, one action)
What comes next
Hub: The 6-Month Learning Plan
Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.