32The growth zoo — Big-O, and its cousins

In Chapter 31 we threw the stopwatch out and started counting the work an algorithm does instead — a number that doesn't care which laptop it runs on. Here we give that number its name and its grammar. First we take one real operation-count and watch a single term of it grow until it swallows everything else, then give what survives a two-character name. After that we line the whole family up on one pair of axes, from the tame to the monstrous. All the way through, we keep asking the one question that turns counting into judgement: if I double n, what happens to the work? By the end you'll look at a loop and say its growth out loud — O(n), O(n²), O(log n) — without running a line. You'll know why we throw away the "3" in 3n² and the whole +100n+7 behind it, and why that's not sloppiness but the plainest honesty about what breaks at scale. And you'll meet the growth zoo, nine animals from the tame O(1) to the monstrous O(n!), and know on sight which cage your algorithm is in.

01Complexity is a price tag, not a stopwatch

Let's pick up exactly where the stopwatch left us. A stopwatch measures this run, on this machine, this second. Move the same code to a laptop twice as fast and the number just halves. So that number tells you almost nothing durable. What an engineer actually needs is the thing that doesn't flinch when you swap machines: how the work grows as the input grows. That has a name — time complexity — and the language we write it in is Big-O.

The unit is not seconds. It is operations: comparisons, additions, array reads, the elementary steps the machine actually takes. Call the input size n — the length of the playlist, the number of users, the pixels in the frame. Then ask a single question: if I double n, what happens to the number of operations? Linear search through an n-song playlist does, worst case, n comparisons. Double the playlist, and you double the work. We write that O(n) and read it "order n". The machine's speed sets how many operations fit in a second; Big-O sets how fast that count climbs. Those are two different facts, and Big-O is the one that decides whether your program survives contact with a big n.

So Big-O keeps the shape and drops the machine. But it drops something else too — it throws away most of the formula. Watch why that is the honest thing to do →

02Why we throw away the constants and the small terms

Suppose you count a routine's operations exactly and get f(n) = 3n² + 100n + 7. Big-O reports just O(n²). It deletes the coefficient 3, the entire 100n term, and the +7. That looks like vandalism. It is not. At the scale where performance actually matters, one term eats all the others alive. So let's not just assert it — let's count it.

def cost(n):
    return 3*n**2 + 100*n + 7          # an exact op-count, three terms

for n in (1, 100, 1000, 1_000_000):
    total       = cost(n)
    square_part = 3*n**2               # just the n² term
    print(n, f"{100*square_part/total:6.4f}%  is the n² term")

# 1         2.7273%  is the n² term
# 100      74.9869%  is the n² term
# 1000     96.7740%  is the n² term
# 1000000  99.9967%  is the n² term

Line by line: cost(n) returns the full three-term count. For each n we compute the total, then isolate square_part — the contribution of the n² term alone — and print its share of the whole. The story is in the last column. At n=1 the n² term is a rounding error: 2.7% of the work. By n=1000 it is 96.8%. At a million it is 99.9967%, and the 100n and the +7 together are three parts in a hundred thousand. Reporting anything but n² would be describing the dust and ignoring the mountain. That is the rule, and now you have watched it come true. Keep only the fastest-growing term, and drop its constant multiplier. The constant shifts the curve up and down, but it cannot change which term wins the race to infinity.

03Read the code: count the deepest nest

You almost never count exact operations. Instead you read structure, and three rules cover most code you will ever meet:

• Sequential blocks add. Do an O(n) pass, then another O(n) pass — that's n + n = 2n, which is O(n). Work done one-after-another sums, and the sum's Big-O is just its biggest piece.
• Nested loops multiply. A loop over n inside a loop over n runs the inner body n × n = n² times. Each level of nesting multiplies in another factor of n. Three deep is O(n³).
• Halving gives log n. A loop that throws away half of what's left each step reaches the end in log₂ n steps, not n. That's the whole magic of binary search.

That leaves one sticky-note rule to rule them all: find the most deeply nested piece of work, count how many times it runs, and that dominates the answer. Everything shallower is a lower-order term you're about to drop anyway.

The halving rule deserves a proof, because log n is the hinge that separates "instant" from "impossible" all over this volume. Watch a million collapse to a handful of steps:

n = 1_000_000
steps = 0
while n > 1:
    n //= 2          # throw away half of what's left, every step
    steps += 1
print(steps)         # 19        ← that's it. one million → 19 steps
import math
print(math.log2(1_000_000))   # 19.931568569324174

Line by line: we start at a million and keep integer-halving until nothing is left to split. It takes 19 steps, because log₂(1,000,000) ≈ 19.93 and you can't take a fraction of a step. Halving is doubling run backwards: 2¹⁰ ≈ a thousand, 2²⁰ ≈ a million, 2³⁰ ≈ a billion. So every time you multiply n by a thousand, a halving algorithm needs only ten more steps. That is why a database can find one row among a billion with about thirty comparisons, and why binary-searching your bug — delete half the code, does it still break? — beats reading every line.

Three rules, and you can read most code's cost off its shape. But "O(n) worst case" hid a word — worst. What about the best case, and the typical one? Meet Big-O's two cousins →

04Big-O, Ω, Θ — the upper, the lower, the tight

Big-O is precisely one thing: an upper bound. "This algorithm grows no faster than g(n)." It is a promise about the ceiling — the worst that can happen. But a full description of an algorithm has three walls, and each has its own name:

• O (Big-O) — the ceiling. Grows no faster than this. The worst case. "It will never be slower than O(n)."
• Ω (Big-Omega) — the floor. Grows no slower than this. The best case. "It can't do better than Ω(1)."
• Θ (Big-Theta) — the tight sandwich. When the ceiling and floor are the same shape, the algorithm is Θ(g(n)) — pinned from both sides. This is the strongest, most honest statement you can make.

Linear search makes it concrete. Best case, the song is first in the playlist: one comparison, Ω(1). Worst case, it's last or missing: n comparisons, O(n). The two walls are different shapes, so there is no single Θ for "one run." But averaged over a random position, it does about n/2 comparisons — still Θ(n) on average, because n/2 is just n with a constant we drop. In casual speech everyone says "Big-O" and means "the tight bound," and usually gets away with it. Knowing all three lets you be exact when it counts.

05The growth zoo — from cheap to catastrophic

Here is the entire cast, ordered by how fast the cost climbs. Learn this ladder cold. Ranking two algorithms is often just asking "whose class is lower on this list."

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Curves are pretty, but the shock is in the numbers. Below is the "how big can n be in one second" table. It uses a measured rate for CPython 3.12 on this machine: a tight Python loop runs roughly 3×10⁷ simple steps per second (I ran it — ~3.17×10⁷, best of five — and it's heavily machine- and language-dependent; compiled C would be 10–100× more). What matters is not the exact rate but the gaps between the rows:

Read the third column slowly. An O(n) algorithm chews through thirty million items a second. Drop to O(n²) and that collapses to about 5,600. Drop to O(2ⁿ) and you're stuck at 25, where one more item doubles the time. At O(n!), ten items is already the edge of the world, and eleven takes eleven times longer than ten. This is why "just brute-force it" quietly stops being an option, and why finding a smarter algorithm can be worth more than a thousand faster machines.

You now hold the map of the whole zoo. The last thing to install isn't a fact — it's a reflex, the one that turns all this into the way you attack a problem you've never seen →

06The move: think in growth, hunt the exponent

Everything above collapses into one mental reflex — the move this whole volume is here to install. Faced with any new problem, before you write a line, ask these three questions in order:

• What is my n? Name the thing that grows — rows, users, pixels, moves. If nothing grows, complexity is irrelevant and you should just write the clear version.
• What curve am I on? Read the deepest nest. A nested loop over the same data is a quiet O(n²) — fine at n=100, a fire at n=100,000.
• Can I drop to a lower curve? This is the entire game. Sorting first to enable binary search trades O(n²) for O(n log n). A hash table (write it down once, look it up free) turns a repeated O(n) scan into O(1). Remembering answers instead of recomputing them turns exponential recursion linear — you'll see naïve Fibonacci fall from O(2ⁿ) to O(n) that way in a later chapter.

That is the difference the volume's opening promised. The mediocre engineer optimises the constant — a faster loop, a cleverer line. The strong engineer changes the curve, and a curve change beats every constant once n is big enough. It even leaks into ordinary life. You binary-search a bug — does it still break with half the code gone? You hash instead of re-derive, writing down the answer so you never solve it twice. You refuse to re-solve what you already solved. Complexity thinking isn't just for code; it's a way of noticing where effort is being wasted as things scale.

You can now price an algorithm in time. But time is only half the bill — every algorithm also spends memory, and the two trade against each other in ways that decide real systems. The next chapter opens the second ledger: space complexity, the stack versus the heap, and why an O(n)-time algorithm can still blow up your RAM →