31What "fast" really means

In Volume 1 we built the machine from the switch up and taught it to run our code. Ever since, the only question that mattered was does it work? Opening Volume 3, we ask the sharper one: is it fast enough to survive? The obvious way to answer that is seconds on a stopwatch, and it turns out that way is a trap. Here's the plan. First we'll time the exact same work seven times and watch the clock hand back seven different answers. Then we'll pin down why the machine itself makes that unavoidable. Then we throw the stopwatch out and start counting the work an algorithm does instead, a number that doesn't care which laptop it runs on. And the whole way through we keep asking the one question that actually matters — not how long did this take, but how does its cost grow as the input grows? By the end you'll look at a loop and count its operations without running it. You'll tell whether it will still be breathing at ten million items. And you'll know exactly why "it runs fine on my laptop" is the most expensive sentence in software.

Before we run anything, let's pin down the word this whole volume orbits. An algorithm is just a recipe: a finite list of steps that turns an input into an answer. Sum these numbers, sort these songs, find this name — each one is a recipe you could follow by hand on paper. The machine matters too, and it helps to keep the two separate in your head. The recipe says what steps to take, and the kitchen decides how fast each step happens. A 2 GHz laptop is a kitchen that ticks two billion times a second, while an older one ticks slower. Same recipe, different kitchens, different clock readings. And Python adds a wrinkle of its own, because the interpreter is part of the kitchen too: CPython spends its own instructions carrying out each step of your recipe. Hold onto that split, because this chapter is the story of learning to judge the recipe on its own. The kitchen keeps trying to sneak into our measurements, and we're about to catch it red-handed.

01The stopwatch is a liar

Let's start with the most honest experiment there is. Here's a tiny function that adds up the numbers 0, 1, 2, … n-1 and does nothing else. We'll call it seven times in a row, on one machine, doing byte-for-byte identical work every time. No network, no disk, no randomness anywhere, so the readings should surely agree. If timing can't give one answer for the same work on the same box, it can't be our measure of "fast." Watch what the stopwatch tells us, because it's about to lie straight to our face.

import time

def work(n):
    total = 0
    for i in range(n):     # exactly n additions, every single run
        total += i
    return total

n = 2_000_000
for _ in range(7):
    t0 = time.perf_counter()
    work(n)                # the identical call, the identical work
    ms = (time.perf_counter() - t0) * 1000
    print(round(ms, 1))    # 67.3 · 67.4 · 68.5 · 67.2 · 68.1 · 67.7 · 66.6

Line by line: work(n) runs a loop that does the same n additions no matter what. time.perf_counter() reads a high-resolution clock before the call and again after it. The difference, times 1000, is the elapsed time in milliseconds. We ran it and got seven different numbers, from 66.6 ms up to 68.5 ms, for byte-for-byte the same work. Seven honest readings, seven answers — that experiment fails the most basic test of a measurement. The spread was only about 3% here, because the machine was nearly idle. Open a browser, start a video call, or run this on a loaded server. Now the slowest reading can be several times the fastest. (These are wall-clock times on one specific Intel machine, and yours will differ — which is exactly the point.)

A fair objection: why not just average the seven runs and call that the answer? Averaging does help, and real benchmarking tools do exactly that, so the instinct is sound. But look at what the average actually pins down: how fast this code runs on this machine, under today's load, with this Python version. Change any of those and your carefully averaged number is stale. Your teammate's laptop gives a different average, and the production server gives a third. So a measured time is a fact about one kitchen on one afternoon, however carefully you take it. It can never be a portable fact about the code itself. We want a number we can write in a book, hand to a stranger, and have it stay true on their machine. The stopwatch, averaged or not, cannot give us that, so something else will have to. That is the trade this chapter makes: give up the seconds, keep the certainty.

Why does the clock wobble? Recall Volume 1's machine: the CPU runs at some clock rate, and it keeps its hot data in a small fast cache. Crucially, the core is also shared, so the operating system constantly pauses your program to give other processes a turn. Your program is a guest on the machine, and guests don't control the schedule. That means the seconds you measure are really operations × time-per-operation, and the second factor belongs to the machine. It is set by the hardware and by whatever else the box happens to be doing this millisecond. Change the laptop, change the load, or change nothing at all and run it again — the seconds move. Seconds measure the kitchen, not the recipe.

It's worth seeing that pause with an engineer's eyes, because it is wonderfully concrete. The operating system keeps a scheduler, a piece of code that decides which process owns each core right now. Many times a second it steps in, saves your program's registers to memory, and hands the core to someone else. Your program doesn't even know it happened, and that's the beautiful part. From the inside it just ran, yet the wall clock kept ticking through every interruption. Worse, the other process fills the cache with its own data while it runs. When your program gets the core back, its first memory reads miss the cache and crawl out to slow RAM. So two runs of identical code genuinely execute differently at the metal, down to the cache lines. The wobble in our seven numbers isn't sloppy measurement. It's the true story of a shared machine, measured honestly. None of this is Python's fault, by the way, because a C program on the same box wobbles for exactly the same reasons.

If seconds are the wrong yardstick, what is the right one? The blue number that never flinched →

02Count the work, not the clock

The fix is to stop timing and start counting. Pick the operations the algorithm actually performs — a comparison, an addition, a swap, a pass of the loop. Then count how many of them it does as a function of the input size. That count is a fact about the algorithm itself, not about the machine that happens to run it. It doesn't care about your clock speed, your cache, or the video call in the background. Run it on a supercomputer or on a calculator from 1995 and the count is the same integer. That's the number we'll learn to read straight off the code.

Now, an honest objection before we go further: not all operations cost the same nanoseconds. On a real CPU an integer addition is cheap, while a memory fetch can cost many times more. So isn't calling each one "one unit" a lie? It's a deliberate simplification, we should label it as exactly that, and here's why it earns its keep. The per-operation price is a kitchen fact again: it changes with the chip, the cache, the compiler. The count of operations is the recipe fact, and it's the part that explodes when inputs grow. Blurring a 2× difference between operation types costs us little, because we're hunting differences of a million times, not two. In practice you count the operation that runs most often, treat it as one unit, and move on. We'll sharpen this bookkeeping in the next chapter, but for now one step is one unit, on purpose.

Two words we will lean on for the whole volume. n is the size of the input — the number of songs in the playlist, rows in the table, pixels in the image. It is the one knob everything turns on. A basic operation is a single step we agree to treat as one unit of work. Now count the sum loop:

def work_counted(n):
    total = 0
    ops = 0
    for i in range(n):
        total += i
        ops += 1           # tally one addition per pass
    return ops

print(work_counted(10))         # 10
print(work_counted(2_000_000))  # 2000000  — the same on every machine, every run

The loop body runs once per value of i, and there are n values, so it does exactly n additions. Notice that we didn't time anything — we counted, and counting is exact. For n = 10 the answer is 10, and for n = 2,000,000 it is 2,000,000. Three runs in a row gave the identical number, because unlike the clock, a count is reproducible on any machine you like. This algorithm's cost is n: double the input, and you double the work. That sentence, "double the input, double the work", is a complete, machine-independent description of how this code behaves. And we got it without a stopwatch anywhere in sight.

Try the counting move on two quick variations, because it should feel mechanical by now. Suppose each pass of the loop did an addition and a comparison, two units instead of one. The cost becomes 2n: at n = 10 that's 20 units, and at n = 20 it's 40. Now suppose the loop steps by two, visiting only every other number. The cost becomes n/2: 5 units at n = 10, then 10 units at n = 20. Check yourself with a pencil: at n = 40 the three costs are 40, 80, and 20, each exactly double their n = 20 values. Notice what stayed the same in every version. Doubling the input doubled the work every single time, whether the cost was n, 2n, or n/2. Those constant factors move the line up or down, but they never change its shape. That shape is the thing we're learning to read, and the next section shows a shape that behaves very differently.

you type
# ---------- stopwatch.py: seven brackets around identical work ----------
$ python stopwatch.py

# ---------- the same work through timeit: repeat 7, report min/max/mean ----------
$ python -c "import timeit, stopwatch as s
ts = timeit.repeat(lambda: s.work(2_000_000), number=1, repeat=7)
print('best  %.1f ms' % (min(ts)*1000))
print('worst %.1f ms' % (max(ts)*1000))
print('mean  %.1f ms' % (sum(ts)/len(ts)*1000))"

# ---------- and from the shell, ch29's form ----------
$ python -m timeit -s "from stopwatch import work" "work(2_000_000)"

# ---------- now the count, three times in a row ----------
$ python -c "from count import work_counted
print([work_counted(2_000_000) for _ in range(3)])" 

you see
$ python stopwatch.py
[76.9, 84.0, 87.7, 86.3, 85.2, 87.3, 82.6]
spread: 14.0 %

$ python -c "... timeit.repeat(..., repeat=7) ..."
best  86.1 ms
worst 91.2 ms
mean  89.6 ms

$ python -m timeit -s "from stopwatch import work" "work(2_000_000)"
:0: UserWarning: The test results are likely unreliable. The worst
time (400 msec) was more than four times slower than the best time
(87.6 msec).
5 loops, best of 5: 87.6 msec per loop

$ python -c "... [work_counted(2_000_000) for _ in range(3)] ..."
[2000000, 2000000, 2000000]

03It's the growth that bites, not the number

Knowing an algorithm costs "1000 operations at n = 1000" is nearly useless on its own. The question that matters is: when n gets bigger, how fast does the cost grow? Because inputs always get bigger. Today's 1000 songs are tomorrow's million. Watch what happens when we put one loop inside another — the playlist code that compares every song against every other song, to find duplicates say:

def nested_ops(n):
    ops = 0
    for i in range(n):
        for j in range(n):    # a full inner sweep for EVERY outer step
            ops += 1
    return ops

for n in (5, 100, 1000):
    print("n =", n, " single loop:", n, " nested:", nested_ops(n))
# n = 5     single loop: 5     nested: 25
# n = 100   single loop: 100   nested: 10000
# n = 1000  single loop: 1000  nested: 1000000

The outer loop runs n times, and for each of those the inner loop runs a full n times. So the body fires n × n = n² times in total. We ran it, and at n = 5 the two loops are still close: 5 vs 25. At n = 100 they are 100 vs 10,000, and at n = 1000 they are 1000 vs a million. The single loop and the nested loop start life as near-neighbours and end up in different universes. That divergence, not any single value, is what decides whether your code survives its own success. And success, here, just means growth: more users, more songs, more rows, more n.

Here's why the square has to appear, so it never feels like a trick. Draw the work as a grid: one row per outer pass, one column per inner pass. With 5 songs you get 5 rows of 5 checks each, and 5 × 5 = 25 cells. That grid is literally a square, which is why this growth is called quadratic, from the Latin for square. Every time you add one song, you don't add one cell. You add a whole new row and a whole new column. At n = 1000 the grid holds 1000 × 1000 = a million cells, exactly the million we measured. A thousand-song playlist becomes a million-cell grid of checks, all from one innocent-looking nested loop. Step the walkthrough above and watch the inner counter restart from zero on every outer pass. That restart is the whole story: the inner loop refuses to remember its previous laps, so the work multiplies instead of adding.

Fine — count the operations and watch the growth. But count for which input? The luckiest one, or the cruelest? →

04Best, worst, average — plan for the bad day

Most algorithms don't do the same amount of work on every input of size n. Search a playlist for one song, scanning from the top and stopping when you find it. If the song sits at the first track, you make exactly one comparison and stop. If it's the last track, or missing entirely, you make all n. Same code and same n, yet wildly different cost, depending on the arrangement of the data. So we give the possibilities names, and we call them the three cases.

def scan(playlist, target):
    comparisons = 0
    for song in playlist:
        comparisons += 1
        if song == target:
            return comparisons     # found it — stop early
    return comparisons             # fell off the end — not found

data = list(range(1000))                   # a 1000-item playlist
print(scan(data, 0))       # 1     BEST:    target is first
print(scan(data, 999))     # 1000  WORST:   target is last
print(scan(data, 1234))    # 1000  WORST:   target isn't there at all
from statistics import mean
print(mean(scan(data, s) for s in data))   # 500.5  AVERAGE over all present items

Best case is the luckiest input the algorithm can meet: target first, 1 comparison, the smallest cost it can get away with. Worst case is the cruelest input, with the target last or absent, costing all 1000 comparisons. That is the most work the algorithm can ever be forced to do. Average case is the expected cost over typical inputs, and we measured it honestly. We searched for each of the 1000 present songs once, and the mean came out at 500.5 comparisons. That is roughly n/2, which makes sense, because a random hit lands halfway down on average. All three are real, verified numbers from the run above, not textbook estimates.

Two of those numbers deserve a second look. First, the mean of 500.5 is not mysterious: the costs of the 1000 searches were simply 1, 2, 3, … up to 1000. Averaging a straight run of numbers gives the midpoint, (1 + 1000) / 2 = 500.5, and that's the whole calculation. Second, and this is the engineering habit: when the three cases disagree, plan on the worst. The best case is luck, and luck is not a design input. The average case leans on an assumption — that every song is equally likely to be asked for — and real users break assumptions daily. Only the worst case is a guarantee, a ceiling the algorithm cannot break no matter how cruel the input. When an engineer promises "this responds in under a second," it's the worst case doing the promising. Volume 3 will therefore speak mostly in worst cases, and now you know that's caution, not pessimism.

Now we can state the yardstick precisely — and use it to defuse the most dangerous sentence a programmer ever says →

05"It runs fine on my laptop"

Here is the whole chapter's payoff, and it is genuinely scary. Take that nested n² loop. On this machine each inner step costs about 28 nanoseconds (measured: the n = 1000 run took 28.2 ms for a million steps). Now watch what the same code does as we feed it more data:

per_op = 28.16e-9              # seconds per inner step, measured on this machine

for n in (100, 10_000, 10_000_000):
    steps = n * n              # the nested loop runs the body n × n times
    seconds = steps * per_op
    print(n, steps, seconds)
# n=100        steps=10,000              -> 0.0003 s      a blink
# n=10,000     steps=100,000,000         -> 2.8 s         a pause
# n=10,000,000 steps=100,000,000,000,000 -> 2,816,000 s ≈ 32.6 DAYS

The demo runs at n = 100 and finishes in a third of a millisecond — instant. Ship it. Then real data arrives, and now there are ten million items to handle. The input got 100,000× bigger, but the work is n², so the work got 100,000² = ten billion times bigger. The "instant" program now needs a month to finish a single run, and nobody changed a line of code. Read that again, because it is the whole trap: same code, same correctness, and growth alone did this. For contrast, a single pass over those same ten million items (cost n, not n²) took 312 ms in our test. That means the smarter algorithm is roughly nine million times faster on the exact same hardware. That gulf is what this whole volume is for.

Don't take "a month" on faith, because the whole point of this chapter is that you can check it. At n = ten million, n² is 10⁷ × 10⁷ = 10¹⁴ steps, a hundred trillion of them. Each step costs about 28 nanoseconds on this machine, so the total is 10¹⁴ × 28 ns = 2.8 million seconds. A day holds 86,400 seconds, and 2,800,000 / 86,400 comes out near 32 days. That's the month, derived on the back of an envelope from one small measured run. And this is the superpower worth noticing: we predicted a catastrophe without suffering it. Nobody has to sit through a 32-day run to learn the design is doomed. Count the steps, multiply by one honest measurement, and the future of the program is readable in advance. Keep that envelope habit, because we'll use it on every algorithm this volume meets.

So the real skill isn't timing code. It's reading its shape before it ever runs. That's a way of thinking — let's name the move →

06The one question that turns a coder into an engineer

Everything we have done so far collapses into a single reflex you can carry. When a beginner meets a piece of code, they ask "how long did it take?" That is a question about the kitchen, and its answer changes with every machine and every mood. The engineer asks "how does its cost grow as n grows?" That is a question about the recipe, and its answer is fixed forever. That swap, from measuring the run to reading the growth, is the mental move this whole volume installs. It is also why we could predict a 32-day runtime without waiting 32 days. From here on, every chapter in this volume asks that one question of a new family of algorithms.

The idea that you could separate the algorithm from the machine is not obvious. Somebody had to invent it. It's the heart of what's called asymptotic analysis. Donald Knuth brought it into computing and championed it in The Art of Computer Programming. The move is to judge an algorithm by how it behaves as n heads toward infinity. At that extreme the constant, machine-specific noise falls away, and only the growth remains. Knuth's bet was that the shape you find out there tells the truth about every realistic n too. The way of thinking underneath is worth stealing wholesale: to understand a system, find the one variable it scales with, then ask what happens when you push that variable to the extreme.

And here's the friendly part: you already run this analysis off the computer. You weigh whether to phone ahead or just drive to all five shops. You sense that inviting "a few more" people is fine, but that inviting "everyone" is not. You know a chore that's quick for one week's laundry becomes a nightmare for a year's. That instinct is growth-rate intuition, and you use it every day without ever naming it. This volume takes that instinct, makes it exact, and gives it a precise language to speak. By the end, you'll aim it at code as naturally as you aim it at errands.

# ---------- the two functions, each carrying its own counter ----------
import math

def linear_search(data, target):
    ops = 0
    for i, x in enumerate(data):
        ops += 1                       # one comparison per item, always
        if x == target:
            return i, ops
    return -1, ops                     # fell off the end

def binary_search(data, target):       # data must be SORTED
    ops = 0
    lo, hi = 0, len(data) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        ops += 1                       # one comparison per halving
        if data[mid] == target:
            return mid, ops
        if data[mid] < target:
            lo = mid + 1               # throw away the left half
        else:
            hi = mid - 1               # throw away the right half
    return -1, ops


# ---------- worst case at three sizes: the target is absent ----------
print("n          linear   binary   log2(n)   ratio")
for n in (1_000, 100_000, 10_000_000):
    data = list(range(n))
    _, lin = linear_search(data, n + 1)
    _, bin_ = binary_search(data, n + 1)
    print("%-10d %-8d %-8d %-9.2f %d" % (n, lin, bin_, math.log2(n), lin // bin_))

n          linear   binary   log2(n)   ratio
1000       1000     10       9.97      100
100000     100000   17       16.61     5882
10000000   10000000 24       23.25     416666

#   linear  = exactly n. every item, every time, no early exit available.
#   binary  = log2(n), rounded up and give or take one, because each pass
#             halves what is left: 1000 -> 500 -> 250 -> ... -> 1.
#   The predictions were checkable BEFORE the run, and they held.


# ---------- the doubling test ----------
prev_l = prev_b = None
for n in (1_000, 2_000, 4_000, 8_000):
    data = list(range(n))
    _, lin = linear_search(data, n + 1)
    _, bin_ = binary_search(data, n + 1)
    ...

n=1000   linear 1000   -       binary 10  -
n=2000   linear 2000   x2.0    binary 11  +1
n=4000   linear 4000   x2.0    binary 12  +1
n=8000   linear 8000   x2.0    binary 13  +1

#   Double n, and linear MULTIPLIES by 2. Binary ADDS 1.
#   Inevitable from the code: linear's loop body runs once per item, so
#   twice the items is twice the body. Binary's loop discards half the
#   remaining range per pass, so twice the data is exactly ONE more
#   discard before it is down to a single candidate.


# ---------- question 1: where linear wins ----------
data = list(range(1_000_000))
linear, target at index 0 : 1 comparisons
binary, target at index 0 : 19 comparisons
linear, target absent     : 1000000 comparisons
binary, target absent     : 19 comparisons

#   Linear beats binary 1 to 19 when the target sits in slot 0 -- and
#   that is exactly the BEST case, which section 04 told us is luck, not
#   design. Look at the same table's worst-case row: 1,000,000 against 19.
#   Quoting the best case is how benchmarks lie. The guarantee is the
#   ceiling, and binary's ceiling is 19 where linear's is a million.


# ---------- question 2: what the stopwatch could never give ----------
data = list(range(100_000))
[linear_search(data, 100_001)[1] for _ in range(3)]  -> [100000, 100000, 100000]
[binary_search(data, 100_001)[1] for _ in range(3)]  -> [17, 17, 17]

#   Three runs, zero variation. No warm-up, no "best of five", no
#   background-load caveat, and nothing to average. The count is a
#   property of the algorithm; the milliseconds were a property of the
#   afternoon. That is the whole trade this chapter makes.


# ---------- question 3: why linear is still fine at n = 200 ----------
#   Worst case, linear does 200 comparisons; binary does 8. Both are
#   invisible at ~10 ns a comparison: 2 microseconds against 0.08.
#   Growth is about the shape as n climbs, not about winning at n = 200.
#   And binary needs SORTED input, which costs O(n log n) to produce.
#   Sorting 200 songs to save 192 comparisons once is a loss. Sort once
#   and search a million times, and it is the best trade in the volume.

We have the idea: count operations, watch the growth, design for the worst case. Now we give that growth a precise name and a notation — meet Big-O, the symbol that lets you say "n²" out loud and have every engineer on earth know exactly what you promised. That's Chapter 01. →