Amortised analysis

Most calls to append take one step, but now and then one takes very many steps. Amortised analysis looks at the total cost of many operations, and shows that the average cost per operation is small, even in the worst case.

A list that grows

A Python list keeps its values side by side in one block of memory. That is what makes a[i] fast: the computer works out where value i is from where the block starts (ARRS-1). But a block cannot simply get longer, because the memory after it may already be in use.

So a list sets aside more room than it needs. While there is spare room, append writes the value into it, which is one step. When the room runs out, the list gets a new, bigger block and copies every value across. That one append costs n steps.

Total cost over many appends

Count the whole cost of n appends, starting from an empty list that doubles when full. Each append writes one value: n writes. The copies happen when the size reaches 1, 2, 4, 8, and so on, up to at most n. They copy

values, where 2ᵏ is the last copy size, which is at most n. So n appends cost fewer than n + 2n = 3n steps. Spread over n appends, that is fewer than 3 steps each. We say append is amortised O(1).

This is a worst-case promise about the total, not a guess about likely inputs. Any sequence of n appends costs O(n). One single append can still cost Θ(n).

The banker’s view

A second way to see the same result: charge every append 3 coins instead of 1. One coin pays for writing the value. The other two are saved with it.

Just after a copy into a block of size 2m, the list holds m values and has no coins saved. The next m appends each save 2 coins, which is 2m coins. At that point the block is full, and the copy of 2m values is paid for by the 2m saved coins. Coins never run out, so 3 coins per append always cover the real cost.

This method is handy when the expensive step is harder to add up directly. The union-find station (DSUF) uses the same kind of argument.

Why double, not add 10

Step through the second version of the figure. If the list adds a fixed amount of room k each time, a copy happens every k appends, and the copies cost k + 2k + 3k + … up to n. That is about n² / (2k), which is Θ(n²) total, or Θ(n) per append.

Any growth by a fixed factor works: doubling, or growing by half, or by an eighth. CPython’s list grows by about one eighth plus a little, which wastes less memory but copies more often. The amortised cost is still O(1).

Now try BIGO-P4, A growing platform, where you build this list yourself and count its copies.