Amortized analysis measures the average cost per operation over a sequence, even when individual operations occasionally cost much more. It explains why a dynamic array's append is "O(1) amortized" despite occasional O(n) resizes.
When a dynamic array fills up, it allocates a new array (usually ) and copies all elements — an O(n) step. But because capacity , expensive copies become exponentially rarer.
Appending into a doubling array (cap shown):
ops: 1 2 3 4 5 6 7 8 9
cap: 1 2 4 4 8 8 8 8 16
copy: * * * * * <- copies at 1,2,4,8,16...
To insert n elements, total copy work =
1 + 2 + 4 + ... + n ≈ 2n (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
arr = []
for i in range(1_000_000):
arr.append(i) # almost always O(1); rarely O(n) during a resize
| Operation | Worst single | Amortized |
|---|---|---|
| append (doubling) | O(n) | O(1) |
Growing by a constant amount would make each insert trigger a copy, giving O(n) amortized. Multiplicative growth is what spreads the cost out.
Amortized analysis gives a fair, realistic picture of performance — without it, you'd wrongly fear that every append or hash-table insert is O(n).
It also justifies a key design rule: grow capacity multiplicatively, which underlies dynamic arrays, hash tables, and string builders everywhere.