34Amortized analysis — the honest average

In Chapter 33 we dropped Big-O through to the metal, and we watched two algorithms with the same cost run a hundred times apart. Here we stay up at the level of the count, but we complicate the count itself. Most algorithms don't have one cost at all. They have a best day, a worst day, and a typical day. The gap between those days can be the gap between "instant" and "the site is down." So here's the plan. First we'll learn to price all three days for the same piece of code. Then we'll meet a subtler idea, the one that trips up almost everyone. How can a single operation be wildly expensive on one call and still be, honestly and provably, cheap? The whole way through we keep asking the one question 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 when we ask how many comparisons does it cost? The honest answer is that it depends on where the target sits. So we don't demand one number, because there isn't one to demand. Instead we ask three separate questions about the same code, and each one has a precise, non-negotiable meaning.

Let's make the three questions concrete before we lean on them. Take a list of 1,000 items and search it for one target. If the target sits in the very first slot, you pay 1 comparison, and that is the best case. If it sits in the last slot, or isn't in the list at all, you pay 1,000 comparisons: the worst case. And if the target is equally likely to be anywhere, you expect the middle, because (1 + 1000) / 2 is 500.5. Call it about 500 comparisons: the average case. Same loop, same code, and the three honest answers span a thousand-fold. Notice that each answer leaned on a different assumption about the input. That's not sloppiness — that's the honest shape of the question.

• 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. Luck is rarely worth designing around. Average case needs an assumption about which inputs will actually show up, and that assumption can be wrong. Worst case needs no assumptions at all, which is exactly what makes it valuable. It is a promise: "no matter what you throw at me, I will not cost more than this." That's why an engineer who says an algorithm "is O(n)" with no qualifier almost always means the worst case. It's the only one of the three you can hand to 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.

Before the code, let's see why a sorted list is poison for this pivot choice. Take five sorted numbers, say [3, 7, 9, 12, 15], with pivot = last element. The pivot is 15, the largest value there is. Partitioning compares the other 4 items against it, and every one of them lands on the "smaller" side. So we paid 4 comparisons and the problem shrank by exactly one item. Repeat the move on the four that remain: 3 comparisons, then 2, then 1. The total is 4 + 3 + 2 + 1 = 10, which is exactly 5·4/2. That's the same triangle-number fingerprint you're about to see at n = 2,000, just small enough to check by hand.

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

Read it line by line: comps tallies each comparison as it happens. qs partitions the slice a[lo..hi] around pivot, sweeping j across the slice and counting one comparison per step. Then it recurses 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 number is exactly 2000·1999/2, the sum 1 + 2 + … + 1999, and it is the fingerprint of a fully lopsided split on every single call. Same algorithm, same n, 79× more work — because the case changed.

Now for the mirror image, and the reason your dict and set feel like magic. A hash lookup is O(1) on average, because it jumps straight to a bucket (Volume 1, chapter 7). Its worst case is a different story: when every key collides into one bucket, the lookup degrades to an O(n) scan. Usually that worst case is a fairy tale you never meet. But you can force it on purpose, 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 against each other. 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, which is the signature of O(n). (The timings are from this laptop, and the shape, not the exact digits, is the point.) And this isn't academic: feeding a web server keys crafted to collide is a real denial-of-service attack called hash flooding. That attack is exactly why modern languages randomize their hash seed at startup.

Now hold the chapter's real puzzle in your hands. Ask any Python programmer what list.append costs and they'll say O(1) without blinking. But you already know, from Volume 1, that a list sometimes runs out of room and must copy every element to a bigger block. That single call touches all n items, which is O(n) by any honest count. By the worst-case rule we just agreed on, the label should therefore be O(n). So is everyone quoting a wrong number?

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, where to amortize a cost is to spread a big one-time expense across many periods. Each period then carries a small, even share. Think of a £1,200 annual subscription: it isn't "£1,200 expensive," because 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. So rare that when you add up the whole bill and divide, the average comes out 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 that any sequence of m appends costs at most c·m in total, guaranteed, for every possible sequence. No luck, no distribution, no coin flips — just a promise.

Run the arithmetic once by hand and the definition stops being abstract. Say a sequence holds 99 cheap operations at 1 unit each, plus one monster that costs 101 units. The whole bill is 99 + 101 = 200 units, spread across 100 operations. Divide, and every operation carries 2 units — a small constant, even though one member of the sequence cost roughly fifty times that. Nothing in that arithmetic was probabilistic: we didn't hope the monster was rare, we counted the whole sequence, monster included.

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 here rather than 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 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 is 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). You can 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), and 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. First, the red spikes get taller: a resize at length 32 copies 32 references, and a resize 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 is amortized analysis in one picture: the individual worst case grows without bound while the per-operation average stays pinned inside a constant band. The next section proves why the line can't rise.

you type
# ---------- capacity.py ----------
$ python capacity.py

# ---------- the empty list, and the two constants in the arithmetic ----------
$ python -c "import sys; print(sys.getsizeof([]))"

# ---------- and the tie back to chapter 33's mysterious 8856 ----------
$ python -c "import sys
g = [[0]*1000 for _ in range(1000)]
print(sys.getsizeof(g[0]), (sys.getsizeof(g[0]) - 56) // 8)" 

you see
$ python capacity.py
len   bytes   slots   copied
1     88      4       0
5     120     8       4
9     184     16      8
17    248     24      16
25    312     32      24
33    376     40      32
41    472     52      40
53    568     64      52
65    664     76      64
77    792     92      76
93    920     108     92
109   1080    128     108
129   1240    148     128
...
861   7832    972     860
973   8856    1100    972

$ python -c "import sys; print(sys.getsizeof([]))"
56

$ python -c "... getsizeof(g[0]) ..."
8856 1100

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 resize copies the block it's leaving. So the copies add up to 1 + 2 + 4 + 8 + … up to roughly m.

Before trusting that sum, check it with numbers small enough to hold. 1 + 2 + 4 + 8 = 15, and twice the largest term is 16. Add the next term and it holds again: 1 + 2 + 4 + 8 + 16 = 31, still under 32. Here's why it must always work: in a doubling series, each term is one more than the sum of every term before it. So the whole tail behind the last term can never even match the last term, let alone exceed it. The final resize you pay for is always bigger than all previous resizes combined. That's the shape that keeps the total bill so small.

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 — 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."

Sanity-check the bound with a sequence you can tally on paper. Sixteen appends into a doubling list pay 16 writes, one per append. The resizes fire when the block is full at sizes 1, 2, 4, and 8, copying that many references each time: 1 + 2 + 4 + 8 = 15 copies. The grand total is 16 + 15 = 31 steps for 16 appends, an average just under 2. The bound said "under 3," and the real tally came in under 2 — the inequality is honest with room to spare. That margin is also why the interactive's amber line hovered around 2 rather than 3.

So much for the clean whiteboard model. Now let's put a real stopwatch on a real million appends and check the promise against CPython itself: 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 on this laptop, though yours will vary. For comparison, writing into a list that's already the right size means pure O(1) writes with zero growth, and that 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.

# ---------- growing_list.py ----------
import sys

class GrowingList:
    def __init__(self, grow=lambda cap: 2 * cap):
        self.slots = [None]                       # capacity 1
        self.n = 0
        self.grow = grow
        self.copies = self.writes = self.resizes = 0

    def append(self, x):
        if self.n == len(self.slots):                  # no spare seats left
            new = [None] * self.grow(len(self.slots))  # rent a bigger block
            for i in range(self.n):                    # move every reference
                new[i] = self.slots[i]
            self.copies += self.n
            self.slots = new
            self.resizes += 1
        self.slots[self.n] = x                         # drop it in the next seat
        self.writes += 1
        self.n += 1

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)
        return self.slots[i]


# ---------- doubling: cap -> 2 * cap ----------
n           resizes  copies      writes    total     total/n
16          4        15          16        31        1.938
1000        10       1023        1000      2023      2.023
10000       14       16383       10000     26383     2.638
100000      17       131071      100000    231071    2.311
1000000     20       1048575     1000000   2048575   2.049

#   The n = 16 row is the chapter's hand tally, reproduced exactly:
#   16 writes + 15 copies = 31 steps, an average just under 2.
#
#   Against the bound: every total/n came in under 3, as proved, and the
#   worst row (2.638) is the one where n sits just past a resize and the
#   list is carrying its biggest slack. The measured number lands near 2,
#   not 3, because the copies alone total 2^k - 1 -- always less than 2n
#   and usually near n. The inequality is honest with room to spare.
#
#   The number that matters: total/n does NOT grow with n. A million
#   appends cost 2.049 per append; sixteen cost 1.938. That flatness IS
#   O(1) amortized -- and notice it took no probability at all.


# ---------- grow by one: cap -> cap + 1 ----------
n           resizes  copies      writes    total     total/n
1000        999      499500      1000      500500    500.5
2000        1999     1999000     2000      2001000   1000.5
4000        3999     7998000     4000      8002000   2000.5
8000        7999     31996000    8000      32004000  4000.5

#   total/n: 500.5 -> 1000.5 -> 2000.5 -> 4000.5. It DOUBLES every time n
#   doubles, which means the per-append cost is proportional to n:
#
#       append is O(n) amortized       (not O(1))
#       building the list is O(n^2)    (the ratio column reads x4)
#
#   And 500500 is the triangle number again: 1 + 2 + ... + 999 = n(n-1)/2.
#   Every single append relocates, copying everything already there.
#
#   ONE CHARACTER moved the whole structure from O(1) to O(n) per
#   operation. The proof in section 05 never depended on the factor being
#   exactly 2 -- it depended on the new block being PROPORTIONAL to the
#   old one, so the copies form a geometric series that sums to under 2n.
#   cap + 1 grows by a constant, the series becomes arithmetic, and an
#   arithmetic series sums to n^2/2 instead. Growth by 1.125x, or 1.5x,
#   or 10x all stay O(1) amortized; growth by "+ k" never does.


# ---------- and what CPython actually does ----------
lst, prev, resizes, copied = [], sys.getsizeof([]), 0, 0
for i in range(1_000_000):
    lst.append(i)
    cur = sys.getsizeof(lst)
    if cur != prev:
        resizes += 1
        copied += i                 # the items already present got moved
        prev = cur

resizes 86   slots copied 8445096   copies/append 8.45   total/append 9.45

#   Our doubling model: 20 resizes, 2.05 writes per append.
#   Real CPython:       86 resizes, 9.45 writes per append.
#
#   CPython grows by only about 1/8 (new = size + (size >> 3) + 6), so it
#   resizes four times as often and copies four times as much. Bigger
#   constant, identical Big-O -- and this counted run reproduces the
#   chapter's stopwatch numbers exactly, from a different instrument.
#   The model told the right story; the machine picked a different
#   constant, and the amortized contract survived both.

At this point a careful reader should feel an itch. "Fast on average" is exactly what we said about hash lookups back in section 02, and that promise turned out to be breakable — one crafted input and it rotted to O(n). Now here we are calling append "fast on average" too. Is amortized O(1) just the same fragile bet wearing a new name? It is not, and the difference is the single most important idea in this chapter. The two "averages" are computed over completely different things.

06The trap: amortized is not average-case

This is the distinction that separates people who've memorized the words from people who understand them. The myth is so common that it is worth killing out loud, right now.

Line them up, starting with Quicksort. Its 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 into n², because the good behaviour was conditional on luck. Now look at append's amortized O(1), where 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, but amortized cannot.

you type
# ---------- presize.py: four ways to build the same million ----------
$ python presize.py

def by_append():        out = []; [out.append(i) for i in range(N)]
def by_presize():       out = [None] * N; out[i] = i ...
def by_comprehension(): return [i for i in range(N)]
def by_list_of_range(): return list(range(N))

# ---------- and how much slack each one ends up carrying ----------
sys.getsizeof(obj), (sys.getsizeof(obj) - 56) // 8

# ---------- now time the ONE append that relocates ----------
lst = list(range(5_000_000))       # exactly 5,000,000 slots: no spares
t0 = perf_counter(); lst.append(0); spike = perf_counter() - t0
# then 1000 more appends, into seats that already exist

you see
by_append               41.2 ms
by_presize              27.1 ms
by_comprehension        31.4 ms
by_list_of_range        17.9 ms

slack carried at the end (1,000,000 items):
  append loop      8448728 bytes   1056084 slots
  [None] * N       8000056 bytes   1000000 slots
  comprehension    8448728 bytes   1056084 slots
  list(range(N))   8000056 bytes   1000000 slots

len 5000000, capacity 5000000 -> the next append must relocate
  the relocating append          7.114   ms
  a quiet append (mean of 1000)  0.000053 ms
  ratio                          x135238

deque(range(100), maxlen=5) -> deque([95, 96, 97, 98, 99], maxlen=5)
array.array('q'), 1000 appends -> 38 reallocations, 8320 bytes

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