Amortized Analysis

Appending to a Python list is described as $O(1)$, but every so often — when the underlying array is full — it has to allocate a bigger array and copy every existing element into it, which is $O(n)$. So is the $O(1)$ claim a lie? No: it is true on average, even though it is false for any single worst-case call. Amortized analysis is the tool that makes that average-case claim rigorous instead of hand-wavy.

The idea: spread the expensive operations over the cheap ones

The trick behind a dynamic array is doubling: when the array of capacity $n$ fills up, allocate a new array of capacity $2n$ and copy everything over. That copy costs $O(n)$, but it only happens once every $n$ appends — right after the array has filled up again. Add up the total cost of $n$ appends: most are $O(1)$, plus one resize costing $O(n)$, giving a total of $O(n) + O(n) = O(n)$ for $n$ operations, or $O(1)$ per operation on average. This is the aggregate method: total cost over a sequence, divided by the number of operations.

A cleaner way to see why doubling (not adding a fixed amount) matters: if the array grew by a fixed 10 slots each time instead of doubling, a resize would still cost $O(n)$ to copy, but now it happens every 10 appends regardless of how big the array already is — giving $O(n)$ total resize cost across roughly $n/10$ resizes, each $O(\text{current size})$, which sums to $O(n^2)$ overall. Doubling keeps resizes exponentially rare as the array grows, which is what keeps the amortized cost constant.

Worked example: appending 8 elements to a dynamic array starting at capacity 1

append #	capacity before	action	cost
1	1	fits	1
2	1	resize to 2, copy 1, insert	2
3	2	resize to 4, copy 2, insert	3
4	4	fits	1
5	4	resize to 8, copy 4, insert	5
6–8	8	fits	1 each

Total cost across 8 appends: $1+2+3+1+5+1+1+1 = 15$. Average cost per append: $15/8 \approx 1.9$ — a small constant, not the $O(n)$ a single resize might suggest. As the sequence grows longer, that average converges toward a fixed constant near 2, regardless of how many appends you do.

Where it shows up

Interviewers ask you to justify why list.append(), hash table insertion, and union-find's path compression are all amortized $O(1)$ rather than worst-case $O(1)$ — being able to explain why with the doubling argument (not just cite the result) is what separates a memorized answer from an understood one. In production, this distinction matters directly for latency-sensitive systems: a market-making loop that appends to a growing buffer can hit an occasional resize-induced latency spike at exactly the wrong moment, which is why low-latency code often pre-allocates capacity instead of relying on amortized growth — see C++ for Low-Latency Trading.