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

In Chapter 31 we threw the stopwatch out and started counting the work an algorithm does. That count is a number that doesn't care which laptop it runs on. In this chapter we give that number its name and its grammar. Here's the plan. We take one real operation-count and watch a single term of it grow until it swallows everything else. Then we hand the term that survives a two-character name. After that we line the whole family up on one pair of axes, from the tame to the monstrous. And the whole 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, as O(n), O(n²), or 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. That isn't sloppiness, but the deepest honesty about what breaks at scale. And you'll meet the growth zoo itself, 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, because it fails in an instructive way. A stopwatch measures this run, on this machine, this second, and nothing more. Move the same code to a laptop twice as fast and the number just halves. So the number tells you almost nothing durable about the algorithm you actually wrote. What an engineer needs is the one measure that doesn't flinch when you swap machines: how the work grows as the input grows. That measure has a name, time complexity, and the language we write it in is Big-O. Hold that phrase in your hand all chapter, because every symbol we are about to meet unpacks it.

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, 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 the answer comes out as f(n) = 3n² + 100n + 7. Big-O looks at that whole expression and reports just O(n²). It deletes the coefficient 3, it deletes the entire 100n term, and it deletes the +7. On first sight that looks like vandalism, a careless shredding of numbers you worked for. It is not, because at the scale where performance actually matters, one term eats all the others alive. So let's not assert the claim, let's sit down and count it happening.

Before we run the numbers, let's make a count like that believable, because nobody hands you a polynomial in real life. Suppose you want to know whether your playlist holds any duplicate songs, so you check every pair. The first song gets compared against the other n-1, the second against n-2, and so on down to one. That sum works out to n(n-1)/2, which for a 1,000-song playlist is 499,500 comparisons. Double the playlist to 2,000 songs and the count becomes 1,999,000, almost exactly four times the work. That quadrupling is the doubling test giving its verdict: a squared law is running the show. Around that squared core, real code always adds housekeeping, a linear pass here and a fixed setup cost there. Stack those together and you get exactly the shape above, a big term wearing a coat of small ones.

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 lives in the last column, so read that column slowly as n climbs. At n=1 the n² term is a rounding error, just 2.7% of the work. By n=1000 it has taken over and owns 96.8%. Watch the middle rows too, because the takeover is not gradual so much as a landslide. At a million it is 99.9967%, which means 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 become 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.

You can check those percentages with nothing but a pencil, and I'd encourage it once. At n=1000 the three terms are 3,000,000, 100,000, and 7, so the total is 3,100,007. Divide 3,000,000 by 3,100,007 and you get 0.9677, which is the 96.8% in the table. Run the same division at n=1 and you get 3 out of 110, or 2.7%. Notice what changed between the two rows: the n² term grew by a factor of a million while the linear term grew only a thousandfold. That mismatch never stops. Whatever head start the smaller terms have, the squared term eventually laps them, and then laps them again. The same landslide happens for any polynomial you will ever count, only the names of the terms change.

Push that same division out to a million and the landslide is total. The n² term is 3×(10⁶)² = 3,000,000,000,000. The linear term is 100×10⁶ = 100,000,000, and the +7 is a whisker on top. Add them and the total is 3,000,100,000,007. Divide the squared term by that total and you get 0.9999667, which is the 99.9967% from the table. Everything that is not the squared term, the whole 100n + 7, amounts to just three parts in a hundred thousand. You did not have to trust the claim; you just watched it settle.

03Read the code: count the deepest nest

You almost never count exact operations by hand. Instead you read the structure of the code, and three rules cover most of what 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.

The three rules look like three separate things to memorise, but really they are one. They collapse into one sticky note: 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, and you were about to drop it anyway. That is the whole skill.

Let's run the rule over three shapes you will meet constantly. A single for loop over a playlist touches each of n songs once, so the answer is O(n). Two loops in a row, one for the longest title and one for the shortest, do n + n = 2n touches, and the constant drops to leave O(n) again. But put one loop inside the other, as the duplicate check did, and the inner line runs n times for each of n outer passes. Now the deepest work fires about n² times, and the whole routine is O(n²). And if you ever nest three deep, the same logic hands you n³ without further ceremony. The distinction that matters is never how long the code looks on the page. It is sequential versus nested, adding work versus multiplying it.

Put a number on that to feel it. Take n = 4. Two loops in a row do 4 + 4 = 8 touches; one loop inside the other fires its inner line 4 times for each of 4 outer passes, so 4 × 4 = 16 touches. Now double the input to n = 8. The sequential pair climbs to 16, a plain doubling, while the nested pair jumps to 64, a fourfold leap. Adding work stays linear; nesting work squares it. That factor-of-four on a single doubling is the n² signature you already met in the duplicate check.

The halving one deserves 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. Here's the way to hold that in your head: halving is just doubling running backwards. Ten doublings carry you past a thousand, because 2¹⁰ ≈ a thousand, while 2²⁰ ≈ a million and 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. It is also why binary-searching your bug, deleting half the code and asking whether it still breaks, beats reading every line. Keep that trade burned in: a thousandfold more data for ten more steps.

If the halving loop still feels abstract, play the oldest guessing game there is. I think of a number between 1 and 1,000, and you guess while I answer only "higher" or "lower." Guessing 1, 2, 3 in order is linear search, and on average it takes about five hundred tries. The smart move is to open with 500, because either answer throws away half the range at a stroke. The candidates shrink from 1,000 to 500 to 250 to 125, and within ten guesses you have cornered the number. Ten is enough because 2¹⁰ = 1,024, which just clears 1,000. The halving loop above is this same game, played against a number line a million long. Whenever a problem lets you discard half the candidates per question, you are holding a logarithm. And that is the shape of every index, every B-tree, every bisect call you will meet later.

you type
# ---------- growth.py: four functions, four curves, one harness ----------
$ python growth.py

def one_pass(d):                     # ?
    total = 0
    for x in d:
        total += x
    return total

def sort_it(d):     return sorted(d) # ?

def all_pairs(d):                    # ?
    best = 0
    for i in range(len(d)):
        for j in range(i + 1, len(d)):
            if d[j] - d[i] > best:
                best = d[j] - d[i]
    return best

curve(one_pass,  100_000)
curve(sort_it,   100_000)
curve(all_pairs,     500)

# bisect is too fast to clock once, so time 100,000 probes per reading
curve_probe(bisect.bisect_left, 100_000)

you see
one_pass   for x in d: total += x
n=100000       2.694 ms   -
n=200000       5.348 ms   x1.99
n=400000      10.693 ms   x2.00
n=800000      26.030 ms   x2.43
sort_it    sorted(d)
n=100000      13.787 ms   -
n=200000      25.507 ms   x1.85
n=400000      53.318 ms   x2.09
n=800000     141.516 ms   x2.65
all_pairs  for i: for j > i
n=500          7.609 ms   -
n=1000        30.108 ms   x3.96
n=2000       113.744 ms   x3.78
n=4000      1299.351 ms   x11.42
probe      bisect_left, 100,000 probes per reading
n=100000      59.892 ms   -
n=200000      61.028 ms   x1.02
n=400000      62.903 ms   x1.03
n=800000      64.496 ms   x1.03

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, on its own, is precisely one thing: an upper bound. It says this algorithm grows no faster than g(n), and it says nothing else. In other words it is a promise about the ceiling, about the worst that can happen. Hold that ceiling image, because the other two walls are about to appear. A full description of an algorithm has three walls, and the three walls have three names:

• 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 the three walls concrete. Best case, the song you want is first in the playlist, so one comparison suffices and the floor is Ω(1). Worst case, the song is last or missing entirely, which costs n comparisons and gives the ceiling O(n). Those two walls are different shapes, so there is no single Θ that describes "one run." But average the song over a random position and you do about n/2 comparisons. That is still Θ(n) on average, because n/2 is just n wearing a constant we drop. In casual speech everyone says "Big-O" when they mean "the tight bound," and usually gets away with it. Knowing all three lets you be exact when it counts.

Where does that n/2 average actually come from? Line up a 10-song playlist and let the wanted song sit at each position with equal odds. If it is first you do 1 comparison, if last you do 10, and the mean over all ten is (1+2+…+10)/10 = 55/10, which is 5.5. That is exactly (n+1)/2, and for a big n it is just n/2 with a harmless +½ riding along. Drop that constant, as Big-O always does, and the average case is Θ(n) — the same shape as the worst case, only half as tall.

It is worth pausing on why engineers quote the worst case at all. A civil engineer rates a bridge by the heaviest load it must survive, not the average car. Software earns the same treatment, because the worst case is the one that pages you at 3 a.m. when someone searches for a song that isn't there. A missing song forces linear search to check all n entries before it can honestly say no. The upper bound is therefore the guarantee, the number you can promise a user no matter what input arrives. Best cases are nice, and averages are useful for planning capacity. But the promise you can sign your name to is the ceiling, and that is why O gets all the airtime.

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 "whose class is lower on this list."

Each rung of that ladder has a resident you already know or will soon meet. O(1) is the dict lookup from Volume 1, where one hash lands on the answer regardless of size. O(log n) is the guessing game from a moment ago, binary search cornering a candidate by halving the field. O(n) is linear search, one honest pass down the playlist, while O(n log n) is where the good sorting algorithms live. The zoo's one strange rung is that O(n log n) sits barely above linear, because a logarithm grows so slowly it almost rides along for free. O(n²) is the nested pair-check we counted, every song compared against every other song. Then comes the cliff, where the polynomial classes end and the explosions begin. O(2ⁿ) means trying every subset, and a mere 20 items already gives 2²⁰, about a million possibilities. O(n!) means trying every ordering, and just 10 items gives 10! = 3,628,800 arrangements. Above the cliff you design algorithms, and below it you mostly pray for small inputs.

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, and it is worth a slow read. Every row answers the same question: at this growth rate, how many items fit through the one-second window? It uses a measured rate for CPython 3.12 on this machine, where a tight Python loop runs roughly 3×10⁷ simple steps per second. I ran it and got ~3.17×10⁷, best of five, though the figure is heavily machine- and language-dependent and 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 — one more item doubles the time. At O(n!), ten items is already the edge of the world; eleven items 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.

Why does one extra item double the work at O(2ⁿ)? Because 2ⁿ is the number of subsets of n things: each item is either in or out, two choices, multiplied together. Three items give 2³ = 8 subsets, few enough to list on one hand. Add a fourth item and every old subset splits in two, with-it and without-it, so the count leaps straight to 16. That is the whole engine of the explosion: 2²⁵ is about 33 million, and 2²⁶ is 67 million, exactly twice. The machine never slowed down; the problem doubled underneath it.

You can rebuild that table yourself, and doing it once makes it unforgettable. The budget is about 3×10⁷ steps in a second, so each row asks how big n can get before the budget runs out. For O(n²), solve n² ≈ 3×10⁷, and the square root gives about 5,500, close to the table's 5,600. For O(2ⁿ), note that 2²⁵ is about 33 million, which just overspends the budget, so 25 items is the edge. One honest caveat belongs here, because Big-O hid the constants on purpose. At small n a constant can still decide the race. An O(n²) routine with a tiny constant can beat an O(n log n) one on fifty items, and real sort libraries exploit exactly that. The curve always wins eventually, but "eventually" has to arrive first.

you type
# ---------- membership, n = 1,000,000, target ABSENT (the worst case) ----------
$ python pricelist.py

lst  = list(range(1_000_000)); random.shuffle(lst)
srt  = list(range(1_000_000))
st   = set(srt)

absent in lst                      # O(n)      -- every item
absent in st                       # O(1)      -- one hash, one probe
bisect.bisect_left(srt, absent)    # O(log n)  -- about 20 probes

# ---------- taking from the front, 100,000 times off 200,000 items ----------
l = list(range(200_000));  l.pop(0)        # O(n) per pop
q = deque(range(200_000)); q.popleft()     # O(1) per pop

# ---------- the top ten of a million (shuffled: no free run for Timsort) ----------
sorted(shuf)[-10:]                 # O(n log n)
heapq.nlargest(10, shuf)           # O(n log k), k = 10

you see
MEMBERSHIP  n = 1,000,000, target ABSENT (worst case)
  x in list          8.286 ms      8.3 ns per comparison
  x in set            20.9 ns      x397405 faster than the list
  x in dict           22.3 ns
  bisect_left        133.2 ns      ~20 probes, not 1,000,000

TAKING FROM THE FRONT  100,000 times off a 200,000 item queue
  list.pop(0)      10358.9 ms
  deque.popleft()     19.2 ms      x539 faster

TOP 10 OF 1,000,000  (shuffled -- no free run for Timsort)
  sorted(x)[-10:]          528.9 ms   O(n log n)
  heapq.nlargest(10, x)     55.0 ms   O(n log k)   x9.62
  sorted(x)[-10:] on ALREADY-SORTED input
                            17.1 ms   Timsort finds one run -> O(n)

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, and installing that reflex is what this whole volume is for. Faced with any new problem, ask three questions in order before you write a line:

• 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 you. The mediocre engineer optimises the constant, hunting a faster loop or a cleverer line. The strong engineer changes the curve, because a curve change beats every constant once n is big enough. The habit even leaks into ordinary life: you binary-search a bug by asking whether it still breaks with half the code gone. You hash instead of re-derive, which just means writing down the answer so you never solve it twice. And you flatly refuse to re-solve anything you have already solved once. None of that required a computer, notice. Complexity thinking isn't only for code but a way of noticing where effort is being wasted as things scale.

# ---------- part 1: read the code first, and predict ----------
#
#   alpha   one pass, and each step is a set add plus a set probe.
#           Both are O(1) (hash, then one probe), so n steps of
#           constant work  ->  O(n).
#
#   beta    sorted(d) is O(n log n) comparisons; the for-loop that
#           follows is O(n) and is a lower-order term we drop.
#           ->  O(n log n).   The whole cost is inside sorted().
#
#   gamma   ONE visible for-loop -- and a hidden one. `x not in out`
#           on a LIST is a linear scan of everything collected so far.
#           Pass k scans about k items, so 0 + 1 + 2 + ... + n-1
#           = n(n-1)/2  ->  O(n^2).  The loop that isn't written as a
#           loop is the `in`.


# ---------- part 2: the harness, ratio and per-item cost ----------
def curve(fn, n0, k=4, reps=9):
    prev = None
    for i in range(k):
        n = n0 << i
        data = list(range(n)); random.shuffle(data)
        t = min(timeit.repeat(lambda: fn(data), number=1, repeat=reps))
        print("  n=%-7d %9.3f ms   %-6s %9.1f ns/item"
              % (n, t*1e3, "-" if prev is None else "x%.2f" % (t/prev), t*1e9/n))
        prev = t

alpha
  n=50000       2.351 ms   -           47.0 ns/item
  n=100000      5.428 ms   x2.31       54.3 ns/item
  n=200000     11.666 ms   x2.15       58.3 ns/item
  n=400000     25.988 ms   x2.23       65.0 ns/item
beta
  n=50000       6.004 ms   -          120.1 ns/item
  n=100000     13.211 ms   x2.20      132.1 ns/item
  n=200000     27.886 ms   x2.11      139.4 ns/item
  n=400000     60.796 ms   x2.18      152.0 ns/item
gamma
  n=500         0.928 ms   -         1857.0 ns/item
  n=1000        3.796 ms   x4.09     3796.1 ns/item
  n=2000       13.626 ms   x3.59     6812.9 ns/item
  n=4000       50.294 ms   x3.69    12573.4 ns/item

#   VERDICT
#     alpha  ratios cluster on 2   ->  O(n)        confirmed
#     beta   ratios cluster on 2   ->  O(n log n)  NOT separated by ratio
#     gamma  ratios cluster on 4   ->  O(n^2)      unmistakable


# ---------- part 3: the two that overlap, and what does separate them ----------
#
#   alpha came in at 2.31 / 2.15 / 2.23 and beta at 2.20 / 2.11 / 2.18.
#   Those bands sit on top of each other. The reason is arithmetic, not
#   sloppiness: doubling n multiplies an O(n log n) cost by
#
#       2 * log(2n)/log(n)
#
#   which at n = 100,000 is 2 * 17.6/16.6 = 2.12. A theoretical gap of
#   6% against a machine whose readings wobbled 14% in chapter 31.
#   The ratio test resolves FACTORS (2 vs 4 vs 8), never logarithms.
#
#   What DOES separate them:
#     - the code. beta calls sorted(); comparison sorting is n log n.
#       That is a proof, and it is free.
#     - a much wider sweep. From n=1,000 to n=1,000,000 the predicted
#       n log n / n gap grows to about 2x -- but that needs a quiet box.
#     - counting, not timing (chapter 31's move): count comparisons
#       inside sorted() with a wrapper class and the n log n is exact.


# ---------- the ns/item column: useful, and not a clean tie-breaker ----------
#
#   gamma      1857 -> 3796 -> 6813 -> 12573.  It DOUBLES every row.
#              Per-item cost proportional to n is the definition of n^2.
#              This column is what makes gamma unmistakable.
#
#   beta       120 -> 152, a 27% climb over an 8x n. Consistent with the
#              log factor, and exactly what n log n should do.
#
#   alpha      47 -> 65, a 38% climb -- and alpha is O(n), which should
#              be FLAT. So the column lies about alpha, and it lies for a
#              reason worth knowing: the set outgrows the CPU cache, and
#              each probe starts missing to RAM. Same operation count,
#              rising cost per operation. Big-O counts operations; the
#              machine charges by the cache line. That is chapter 33,
#              and it is why per-item cost is a hint, never a verdict.

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 →