34Amortized analysis — the honest average

In Chapter 33 we dropped Big-O through to the metal and watched two algorithms with the same cost run a hundred times apart. Here we stay at the level of the count, but we make the count harder. Most algorithms don't have one cost at all. They have a best day, a worst day, and a typical day, and the gap between them can be the gap between "instant" and "the site is down." So here's the plan. We'll learn to price all three, and then meet a subtler idea that trips up almost everyone: how a single operation can be wildly expensive on one call and still be, honestly and provably, cheap. The whole way, we keep asking the one thing that matters — if an operation is sometimes O(n) and sometimes O(1), what is it really costing you? By the end you'll look at list.append, an operation that occasionally copies your entire list, and prove with a stopwatch and a derivation that it costs a constant. That proof is called amortized analysis, and it's one of the most useful ways of thinking an engineer owns.

01One algorithm, three honest questions

Let's start with the simplest search there is: walk a list left to right, compare each item to your target, and stop the instant you hit it (you stepped exactly this in trace T22). Now watch the obvious question fall apart — how many comparisons does it cost? The honest answer is it depends on where the target sits. So we don't ask for one number. We ask three separate questions, and each one has a precise, non-negotiable meaning.

• Best case — the luckiest input. The target is in slot 0; you find it in 1 comparison. Cost that never gets beaten: O(1).
• Worst case — the unluckiest input. The target is in the last slot, or absent entirely; you check all n items. Cost that is never exceeded: O(n).
• Average case — the expected cost over a distribution of inputs. If the target is equally likely to be anywhere, you scan n/2 items on average — still O(n), but with a hidden factor of one-half.

These are three different measurements of the same code — nothing about the algorithm changed, only the input did. Best case is a fact about luck, and it's rarely worth designing around. Average case needs an assumption about which inputs show up, and that assumption can be wrong. Worst case needs no assumptions at all. It is a promise: "no matter what you throw at me, I will not cost more than this." That's why, when an engineer says an algorithm "is O(n)" with no qualifier, they almost always mean the worst case. It's the only one you can hand a stranger.

Fine for a toy search. But does the gap between "typical" and "worst" ever actually change which algorithm you'd pick? Oh, it decides careers. →

02Why the case you measure decides the algorithm you choose

Here is where this stops being bookkeeping. Quicksort (stepped in trace T28) is, on typical data, one of the fastest sorts ever written: on random input it does about n·log₂n comparisons. But that speed comes from a gamble. It picks a pivot and splits the list around it, hoping for two roughly equal halves. Feed it an input that always splits into "one item" and "everything else," and every split does real work while the problem barely shrinks. The cost collapses to O(n²). And the input that triggers this? For the textbook "pivot = last element" version, it's an already-sorted list — the most innocent-looking data imaginable. Let's not take that on faith; let's count the comparisons.

def quicksort_count(a):
    comps = 0
    def qs(lo, hi):
        nonlocal comps
        if lo >= hi: return
        pivot = a[hi]                 # naive: last element is the pivot
        i = lo
        for j in range(lo, hi):
            comps += 1                # count every key comparison
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        qs(lo, i-1); qs(i+1, hi)
    qs(0, len(a)-1)
    return comps

# n = 2000
# random input : 25,335 comparisons    (~ n·log2 n = 21,932)
# sorted input : 1,999,000 comparisons (~ n^2 / 2  = 2,000,000)   -> 79x worse

Line by line: comps tallies each comparison. qs partitions the slice a[lo..hi] around pivot, sweeping j across it and counting one comparison per step, then recursing on the two sides. On 2,000 random numbers it spent 25,335 comparisons — right in the n·log n neighbourhood. On the same 2,000 numbers already sorted, it spent 1,999,000. That is exactly 2000·1999/2, the sum 1 + 2 + … + 1999, the fingerprint of a fully lopsided split every single time. Same algorithm, same n, 79× more work — because the case changed.

Now the mirror image, and the reason your dict and set feel like magic. A hash lookup is O(1) on average: it jumps straight to a bucket (Volume 1, chapter 7). Its worst case, when every key collides into one bucket, degrades to an O(n) scan. Usually that worst case is a fairy tale you never meet. But you can force it, and watch O(1) rot into O(n) in real time:

class Bad:
    def __hash__(self): return 0     # EVERY key lands in the same bucket
    def __eq__(self, o): return self.v == o.v

# average nanoseconds per membership test ("x in the_set"):
# size 1000:  normal set     72 ns      colliding set    69,024 ns
# size 2000:  normal set     72 ns      colliding set   113,662 ns
# size 4000:  normal set     74 ns      colliding set   354,515 ns

Read the two columns. The normal set answers in ~72 nanoseconds whether it holds a thousand items or four thousand — flat, the signature of O(1). The sabotaged set, where every key hashes to 0, gets steadily slower as it grows: the signature of O(n). (Timings are from this laptop; the shape, not the exact digits, is the point.) This isn't academic. Feeding a web server keys crafted to collide is a real denial-of-service attack called hash flooding, which is exactly why modern languages randomize their hash seed at startup.

03Amortized: cheap over a lifetime, not by luck

They're not wrong. They're using a third kind of accounting, and it's the star of this chapter. Amortized cost is the total cost of a whole sequence of operations, divided by the number of operations. The word comes from finance. To amortize a cost is to spread a big one-time expense across many periods, so each period carries a small, even share. A £1,200 annual subscription isn't "£1,200 expensive"; amortized over the year it's £100 a month. The £1,200 charge is real, but no single month feels it.

The magic move is this. Some operations are occasionally expensive but usually trivial, and the expensive ones are rare enough that when you add up the whole bill and divide, the average is small — often a constant. When we can prove that, we say the operation is O(1) amortized. And here's the part that makes it powerful rather than hand-wavy: this is still a worst-case statement. It doesn't say "append is usually fast." It says "any sequence of m appends costs at most c·m total — guaranteed, for every possible sequence." No luck, no distribution, no coin flips. A promise.

Abstract enough. Let's pin it to the one operation you've typed ten thousand times — and finally cash the promissory note the Big-O chapter wrote when it said "append is O(1)." →

04The canonical case: why append is O(1) amortized

You met the machinery in Volume 1, chapter 6, so we'll use it, not rebuild it. A Python list is a dynamic array: a contiguous block of 8-byte reference slots, deliberately over-allocated with a few spare seats at the end. Watch what append normally does. It just drops one reference into the next spare seat — one write, cost O(1), no matter how long the list is. But when the spare seats run out, there's no room to grow in place, because the neighbouring memory is already taken. So CPython rents a bigger block elsewhere, copies every existing reference across, frees the old block, and then writes your new item. That copy touches all n references: cost O(n). Watch the spare seats refill with sys.getsizeof, which reports the container's own byte size:

import sys
lst = []
for i in range(1, 33):
    lst.append(i)
    # container bytes jump ONLY at len 1, 5, 9, 17, 25 …
# capacity sequence as it grows one at a time:
#   4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128 …

The bytes don't climb smoothly. They jump, then hold flat for several appends, then jump again. Each jump is a relocation (an O(n) copy); each flat stretch is a run of cheap O(1) appends landing in spare seats. The relocations get rarer as the list grows, because each new block is proportionally bigger than the last. That "rare, and rarer over time" is the whole trick, and it's exactly the tall-red-bar-among-green picture from a moment ago. This is the concrete shape of a per-operation cost that is mostly constant with occasional spikes. Turn the knob and feel it:

Drag n and notice the two things happening at once. The red spikes get taller — a resize at length 32 copies 32 references, at length 64 copies 64. Yet the amber average line refuses to climb with n. It just wobbles in a tight band around 2, nudged up the instant a resize lands, then settling back as the next run of cheap appends dilutes the cost. Rising spikes, bounded average. That contradiction — the individual worst case grows without bound while the per-operation average stays pinned inside a constant band — is amortized analysis in one picture. The next section proves why the line can't rise.

Two nagging questions remain. Why is the average exactly 2 and not creeping upward forever? And what does the real, non-doubling CPython actually cost? Time to add up the whole bill. →

05The aggregate method: add up the whole bill, then divide

The cleanest way to prove an amortized bound is the aggregate method: compute the total cost of a sequence of operations, then divide by how many there were. No per-operation cleverness, just one big sum. Take m appends into a list that doubles when full. The cheap part is easy: every append does exactly one write, so that's m writes total. The expensive part is all the copying at resizes. With doubling, resizes happen at lengths 1, 2, 4, 8, …, up to m, and each copies the block it's leaving. So the copies are 1 + 2 + 4 + 8 + … up to roughly m.

That sum is the punchline. A doubling geometric series always adds up to less than twice its largest term: 1 + 2 + 4 + … + m < 2m. So all the copying across the entire sequence costs under 2m, and the writes cost m. That's a grand total under 3m for m appends. Divide by m: under 3 per append, a constant. The list can grow to a billion; the average never budges. That is the derivation behind "append is O(1) amortized."

Enough theory. Let's put a real stopwatch on a real million appends and check the promise against CPython: spares, non-doubling growth, and all.

import time
N = 1_000_000
lst = []
t0 = time.perf_counter()
for i in range(N):
    lst.append(i)
print((time.perf_counter() - t0) * 1000, "ms")   # ~= 55 ms  -> ~55 ns / append

# counting the ACTUAL relocations over the same run:
#   resizes            : 86
#   total slots copied : 8,445,096   ->  8.4 copies per append
#   writes per append  : ~9.4        (constant - does NOT grow with N)

A million appends finished in about 55 milliseconds — roughly 55 nanoseconds each (this laptop; yours will vary). For comparison, writing into a list that's already the right size — pure O(1) writes, zero growth — clocked ~50 ns each. So all of CPython's growing, relocating, and freeing added only about 5 ns per append on average. The counters explain why. Across a million appends there were only 86 relocations, and the total copying came to ~8.4 slot-copies per append. That's the honest CPython constant: about 9 writes per append, not the model's 2, because CPython grows by ~1/8 rather than doubling. Smaller growth means more frequent resizes means a bigger constant. But constant it is: independent of N, exactly as promised. The doubling model told the right story; the machine just uses a different constant.

06The trap: amortized is not average-case

This is the distinction that separates people who've memorized the words from people who understand them, and the myth is worth killing out loud.

Line them up. Quicksort's average O(n log n) is a statement about a distribution of inputs: "if your input is random, expect n log n." Hand it a sorted array and the promise evaporates: you get n². The good behaviour was conditional on luck. Now take append's amortized O(1). There is no "if your appends are random." Every sequence of a million appends costs about 9 million writes — the sorted case, the adversarial case, the you-chose-the-inputs-to-hurt-me case, all identical. You cannot construct a bad sequence, because the guarantee is over the sum, not over a typical draw. Average-case can be defeated by a clever enemy; amortized cannot.

You can now price an algorithm three honest ways and prove a spiky operation is secretly cheap. But pricing is diagnosis, not cure. Next: the design loop itself — start with brute force, then ask the one question that turns a coder into an engineer, "where is the wasted work?" — and watch an O(n²) two-sum collapse to O(n) before your eyes. →