Amortized Analysis

Some operations are usually cheap but occasionally expensive. Amortized analysis answers: what's the average cost per operation, taken across a long sequence?

The dynamic array example

Pushing to a $C$++ vector or Python list is usually $O(1)$. But when the underlying buffer is full, the array doubles its capacity and copies every element — an $O(n)$ operation. Worst case for a single push is $O(n)$. Yet the amortized cost is $O(1)$.

Why it works

When the array doubles from $n$ to $2n$, we copy $n$ elements. We can charge each of those $n$ elements one unit of "future copy" credit at insertion time. By the time we double again, every element pays for its own copy. The bookkeeping balances out.

Formal techniques

The aggregate method sums total cost across a sequence of $n$ operations and divides. The accounting method assigns a virtual cost to each operation, banking surplus for future expensive ones. The potential method tracks a non-negative function $\Phi$ over the data structure's state; amortized cost equals actual cost plus $\Delta \Phi$.

Where you'll see it

Hash table resizing, union-find with path compression, splay trees, and Fibonacci heaps all rely on amortized bounds. When someone says "O(1) amortized," they mean the average over many operations is constant, even though individual calls may be slow.