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 a sharper one — is it fast enough to survive? It turns out the obvious way to answer that, seconds on a stopwatch, is a trap. Here's the plan. First we time the exact same work seven times and watch the clock hand back seven different answers. 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 thing 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, tell whether it will still cope at ten million items, and know exactly why "it runs fine on my laptop" is the most expensive sentence in software.

01The stopwatch is a liar

Let's start with the most honest experiment there is. Here's a tiny function. It 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. Watch what the stopwatch tells us. 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 and after. The difference, times 1000, is 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. That 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, and the slowest reading can be several times the fastest. (These are wall-clock times on one specific Intel machine. Yours will differ, which is exactly the point.)

Why does the clock wobble? Recall Volume 1's machine. The CPU runs at some clock rate, keeps hot data in a small fast cache, and — crucially — is shared. The operating system constantly pauses your program to let other processes have the core. So the seconds you measure are really operations × time-per-operation. That second factor is set by the hardware and by whatever else the machine 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.

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 — and count how many it does as a function of the input size. That count is a fact about the algorithm. 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.

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, or 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. We didn't time anything — we counted. For n = 10 the answer is 10. For n = 2,000,000 it is 2,000,000. Three runs in a row gave the identical number. So this algorithm's cost is n: double the input, 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.

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 this: 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 — say the playlist code that compares every song against every other song to find duplicates:

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. We ran it. At n = 5 the two loops are close: 5 versus 25. At n = 100 they are 100 versus 10,000. At n = 1000 they are 1000 versus a million. The single loop and the nested loop start out as near-neighbours and end up worlds apart. That divergence — not any single value — is what decides whether your code survives success.

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, top to bottom, stopping when you find it. If it's the first track, you make one comparison. If it's the last — or missing — you make n. Same code, same n, but wildly different cost, depending on the arrangement of the data. So we name 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 — target first, 1 comparison. It's the smallest cost the algorithm can get away with. Worst case is the cruelest — target last or absent, all 1000 comparisons. It's the most the algorithm can ever be forced to do. Average case is the expected cost over typical inputs. We searched for each of the 1000 present songs once, and the mean was 500.5 comparisons — roughly n/2. That makes sense, because a random hit lands halfway down on average. All three are real, verified numbers from the run above.

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: ten million items. The input got 100,000× bigger. But the work — n² — got 100,000² = ten billion times bigger, so the "instant" program now needs a month to finish a single run. Nobody changed a line of code. 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 volume is for.

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 so far collapses into a single reflex. When you meet a piece of code, a beginner asks "how long did it take?" That's 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's 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 why we could predict a 32-day runtime without waiting 32 days.

The idea that you could separate the algorithm from the machine like this is not obvious. It had to be invented. It's the heart of what's called asymptotic analysis, brought into computing and championed by Donald Knuth in The Art of Computer Programming. The rule is this: judge an algorithm by how it behaves as n heads toward infinity, and let the constant, machine-specific noise fall away. 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 you already do this off the computer. Deciding whether to phone ahead or just drive to five shops. Sensing that inviting "a few more" people is fine but inviting "everyone" is not. Knowing that a chore quick for one week's laundry becomes a nightmare for a year's. That's growth-rate intuition, and you run it every day without naming it. This volume makes it exact, and gives it a language.

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. →