Amortised Analysis & the Cost of Growing

In short: most appends into a dynamic array are cheap, but one in a while the block is full and the append has to copy everything into a bigger block first. Amortised analysis proves that the expensive copies are rare enough that the average cost over any sequence of n appends is still O(1) — by adding up the whole sequence, by charging a fixed toll that banks the change, or by watching a potential function rise and fall. The same move — "bound the whole sequence, not the worst step" — also explains why your BFS's inner loop isn't the O(V²) it looks like.

Eight appends charged 3 tokens each: small bars for cheap appends, one tall bar for the resize spike, and a bank balance row underneath that dips but never goes below zero

In the Big-O lesson you were told that a list's rare full copy "pays for itself". Here you prove it three ways, then use the same argument where it is less obvious: your breadth-first search's neighbour loop, and a stack that shrinks as well as grows.

One operation is occasionally very expensive. Is a sequence of n operations still cheap? Amortised analysis bounds the total cost of the whole sequence and divides by n. It is not a guess about typical inputs; it holds for every sequence.

The spike, measured

Here is a dynamic array of your own, the structure behind Python's list. It keeps a capacity and a size. An append into a spare slot costs 1 (one write). An append into a full block first copies all size items into a block twice as big, then writes: it costs size + 1.

Run it, then edit grow. Change it to return self.capacity + 1 and watch the copies pile up, or to self.capacity * 3 and watch the empty slots.

your code, drawn · array

Your dynamic array. Cheap appends fill spare slots, and each copy buys as many spare slots as it cost, so the bank of 3-per-append never runs dry.

Sixteen appends cost 16 writes plus 1 + 2 + 4 + 8 = 15 copies: 31, under 2 per append. The spikes are real but rare, each twice as far from the last.

Method 1: aggregate — add up the whole sequence

The aggregate method bounds the total directly. With doubling from capacity 1, the copies happen at sizes 1, 2, 4, 8, … up to the largest power of two below n:

1 + 2 + 4 + \dots + 2^{j} < 2 \cdot 2^{j} \le 2n

So n appends cost fewer than n writes + 2n copies = 3n, and each append costs under 3 on average. That is amortised O(1).

python

The worst single append grows with n, but the per-append average stays below 3. That gap is exactly what amortised analysis is for.

What if the block grows by a fixed amount instead of doubling?

What does this print?

capacity, size, copies = 4, 0, 0
for _ in range(20):
    if size == capacity:
        copies += size
        capacity += 4          # grow by 4 slots, not by doubling
    size += 1
print(copies)

Method 2: the banker — charge more than it costs

The banker's method charges every append a fixed price, and saves the change as tokens. The rule is that the bank may never go negative. If it never does, the fixed price is an upper bound on the average.

Charge 3 per append: one token pays for the write, two go in the bank. After the block doubles from c to 2c, the next c appends save 2c tokens before it is full again, exactly what the next copy of 2c items needs.

Step through the ledger for nine appends:

watch it move · grid

Each append pays 3. Cheap appends save 2 each, and a copy spends them, but the balance never goes below zero.

Append 1 fills the only slot for 1, and 2 tokens go in the bank. 2 by 9 table. At row 1, column 0 — value 2. 2 of 18 cells filled.

1 / 8

Method 3: the potential — store the savings in the structure

The potential method makes the bank part of the data structure's state. Define a potential Φ that measures how "charged up" the array is:

\Phi = 2 \cdot \text{size} - \text{capacity}

Right after a doubling, size is half the capacity, so Φ = 0. Each cheap append raises Φ by 2. Just before the next doubling, size = capacity, so Φ = capacity, which is exactly the number of items about to be copied. The amortised cost of one operation is its actual cost plus the change in Φ:

\hat{c} = c + \Phi_{\text{after}} - \Phi_{\text{before}}

A cheap append costs 1 and raises Φ by 2, so its amortised cost is 3. An expensive one costs size + 1, and Φ falls by size − 2 because the capacity doubles, so it also comes to 3. Step through five appends and watch amortised come out the same every time:

step through it

1capacity, size = 1, 0

2for step in range(5):

3 phi_before = 2 * size - capacity

4 cost = 1

5 if size == capacity:

6 cost += size

7 capacity *= 2

8 size += 1

9 amortised = cost + (2 * size - capacity) - phi_before

10print(amortised)

The payoff is that you check one operation at a time rather than a whole sequence. Even the first append, which starts from Φ = −1 (an empty block of 1), comes out at exactly 3, and so does every append after it:

python

Three bookkeeping styles, one fact. Aggregate is quickest when every operation is the same kind; potential scales to structures with several kinds of operation.

How much to grow by

Doubling is not special. Any factor g > 1 gives amortised O(1). The factor trades time against memory: a bigger g copies less often but leaves more of the block empty. The copies per append approach $1/(g-1)$ , and just after a resize a fraction up to $(g-1)/g$ of the block is unused.

python

CPython's list grows by about an eighth, choosing memory over copies; many other languages use 1.5 or 2.

Which growth factor keeps appends at 2 each on average (1 write plus at most 1 copy per item) and never wastes more than half a block? With factor g, an append costs about g/(g−1) on average, and a freshly grown block has g − 1 empty slots for every used one:

factor g	average cost per append	empty slots per used slot
1.125	9	0.125
1.5	3	0.5
2	2	1
3	1.5	2
4	1.33	3

The cost is at most 2 only when g ≥ 2, and the empty part is at most the used part only when g ≤ 2. Doubling is the one factor that sits exactly on both limits, which is why textbooks default to it.

Shrinking without thrashing

Tunebox's undo history is a stack that halves its block when it gets emptier. The obvious rule, "halve when half full", is a trap: at the boundary one pop halves the block, the next push doubles it again, and each costs a full copy:

broken — fix it

Nine edits followed by six undo/redo pairs should cost only the 15 copies of growing to 16 slots. Instead it prints 111, because every undo/redo pair at the half-full line copies 8 items twice.

With the quarter rule the block is half full after any resize, so many cheap operations must happen before the next copy. Amortised O(1) again.

Aggregate analysis on your own BFS

Amortised thinking is not only about arrays. Look at the heart of your breadth-first search from section 5:

python

A nested loop, so O(V²)? No. Each listener is dequeued once, so each follow list is walked once over the whole run: E checks in total, plus V dequeues, O(V + E). That is aggregate analysis: bound the total, not each iteration.

What does this print?

from collections import deque

graph = {"ana": ["ben", "cal", "dia"], "ben": ["cal"], "cal": ["dia", "eli"], "dia": [], "eli": ["ana"]}
seen, queue, checks = {"ana"}, deque(["ana"]), 0
while queue:
    name = queue.popleft()
    for nxt in graph[name]:
        checks += 1
        if nxt not in seen:
            seen.add(nxt)
            queue.append(nxt)
print(checks)

❓ Cross-question — "So is amortised O(1) the same as average-case O(1)?" No. Average case averages over random inputs and can be unlucky. Amortised averages over a sequence of operations on one structure, and it holds for every sequence. An individual append can still take O(n): if one slow request is unacceptable (a real-time audio buffer, say), amortised O(1) is the wrong promise and you need a structure with a true worst-case bound.

Idioms & real-world patterns

Preallocate when you know n

[None] * n or a comprehension builds the block once, with no resizing. Otherwise repeated append is fine: amortised O(1) really is cheap.

⚡ Advanced — incremental resizing

Some hash tables avoid the spike entirely. When they resize, they allocate the new table but move only a few entries on each later operation, so no single call ever copies everything. Every operation is then worst-case O(1), at the price of looking in two tables during the move.

Quick practice

What does this print?

capacity, size, copies = 4, 0, 0
for _ in range(10):
    if size == capacity:
        copies += size
        capacity *= 2
    size += 1
print(copies)

broken — fix it

The amortised cost should settle at a single constant, 3 — the same charge as the banker's method earlier. This prints [2], a different (and wrong) constant, because the potential is missing its factor of 2.

🎯 Your turn

Write append_costs(n), the cost lab's append ledger. Simulate n appends into a dynamic array that starts with capacity 1 and doubles when full. Return the list of each append's real cost: 1 for the write, plus the number of items copied if the block had to grow first.

append_costs(5) → [1, 2, 3, 1, 5]
append_costs(0) → []

Hint — keep capacity and size. Before writing, if size == capacity, the cost gains size copies and the capacity doubles.

Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.

Amortised Analysis & the Cost of Growing

Amortised Analysis & the Cost of Growing

The spike, measured

Method 1: aggregate — add up the whole sequence

Method 2: the banker — charge more than it costs

Method 3: the potential — store the savings in the structure

How much to grow by

Shrinking without thrashing

Aggregate analysis on your own BFS

Idioms & real-world patterns

Preallocate when you know n

⚡ Advanced — incremental resizing

Quick practice

🎯 Your turn

Practice — level up