Amortized Analysis: Why a Dynamic Array's "Occasional Slow Append" Isn't a Bug

Imagine renting an apartment that you outgrow every couple of years. Most days, nothing happens -- you live there, unpack nothing, pack nothing. But every so often you have to rent a moving truck, pack every box you own, and haul everything to a bigger place. If you total up the cost of every moving day and spread it evenly across every single day you lived somewhere, the average daily cost is tiny, even though moving day itself was expensive and disruptive. That's the intuition behind amortized analysis: judging the average cost of an operation across a long sequence of uses, rather than panicking about the cost of the one operation that happens to be expensive.

A dynamic array -- Python's list, Java's ArrayList, C++'s vector -- runs into this exact situation every time you append to it. Under the hood, a dynamic array is backed by a fixed-size block of memory. Appending an item is normally an O(1) operation: drop the new value in the next open slot and update a counter. But once that backing block is full, there's no room left, so the array has to allocate a brand-new, larger block of memory and copy every existing element into it before the append can finish -- an O(n) operation, the moving day.

The reason this doesn't make dynamic arrays slow in practice is the doubling strategy most implementations use: each time the array runs out of room, it allocates a new block roughly twice the size of the old one, rather than just one slot bigger. Because the size doubles, the total amount of copying done across any N appends adds up to roughly 2N element copies, no matter how large N gets. Divide that total copying cost by N appends, and the amortized cost per append works out to a small constant, even though any individual append might have been the expensive one.

This is genuinely different from an average-case argument about typical input, which is a probabilistic claim. Amortized analysis is a guarantee about any sequence of operations, worst case included -- it just measures cost across the whole sequence instead of any single operation in isolation. Reading only the worst-case cost of one append (O(n)) and concluding a dynamic array is a bad choice for frequent appends would be the wrong lesson; the occasional expensive resize is already priced into the cost of every cheap append around it.

The same reasoning explains why hash table resizing doesn't ruin hash table performance either -- it's the identical doubling-and-copying story under a different name. Amortized analysis is the tool that turns "occasionally slow" from a red flag into an expected, already-accounted-for part of how these structures are supposed to behave.