Amortized Analysis

Amortized analysis measures the average cost per operation over a sequence, showing that occasional expensive operations are cheap on average.

Averaging over a sequence

Some data structures have operations that are usually cheap but occasionally expensive. Amortized analysis asks for the average cost per operation across a whole sequence, guaranteeing that the total cost of any sequence of m operations is bounded even though individual operations vary. Unlike average-case analysis, it makes no assumption about input distribution; the bound holds for the worst possible sequence.

The dynamic-array example

Appending to a dynamic array is usually O(1), but when the array is full it doubles and copies everything, an O(n) step. Because the array doubles, the expensive copies are spread far apart, and the total copying over n appends is bounded by 2n. Divided across n appends, that is O(1) amortized per append.

Three methods

• Aggregate method: total cost of the sequence, divided by the count
• Accounting method: charge each operation a fixed amount, banking credit for later expensive ones
• Potential method: define a potential function on the structure's state; amortized cost is actual cost plus the change in potential

Where it applies

Amortized analysis explains the O(1) amortized append of dynamic arrays, the near-constant operations of union-find with path compression, the O(1) amortized operations of splay trees, and the credit-based cost of incrementing a binary counter. It is the right lens whenever cheap operations subsidise rare expensive ones.

Amortized is not average-case

The distinction matters. Average-case cost depends on assuming a probability distribution over inputs and can be violated by an unlucky input. Amortized cost is a worst-case guarantee over a sequence: no matter what operations are requested, the total is bounded, so the per-operation average holds even for an adversary.