Amortized Analysis

Bounding the average cost per operation across a worst-case sequence, even when individual operations are occasionally expensive.

Average over a sequence

Amortized analysis measures the total cost of a sequence of operations divided by the number of operations, giving a per-operation bound that holds even when a few operations are expensive. Unlike average-case analysis, it makes no probabilistic assumption; the bound is over the worst-case sequence. It explains why a dynamic array's append is O(1) amortized despite occasional O(n) resizes.

Three methods

Kronos motion — when

Aggregate: bound the total cost of n operations directly, then divide by n.
Accounting (banker's): charge each operation a fixed amortized cost, storing credit on the structure to pay for later expensive operations.
Potential: define a potential function on the state; the amortized cost is the actual cost plus the change in potential.

Dynamic array example

When a dynamic array doubles on overflow, n appends trigger resizes at sizes 1, 2, 4, ..., copying a total of at most 2n elements. So n appends cost O(n) in total, or O(1) amortized each, even though a single append that triggers a resize costs O(n). The potential method assigns potential 2*size - capacity, which pays for each copy at resize time.

Potential accounting

python

# amortized cost = actual cost + (Phi_after - Phi_before)
# for a doubling array with Phi = 2*size - capacity:
#   cheap append:  actual 1 + dPhi 2      = 3
#   resize append: actual (size+1) + dPhi = O(1)   (capacity jump cancels)

Where it matters

Amortized bounds justify the efficiency of union-find (inverse Ackermann), splay trees (O(log n) amortized), Fibonacci heaps, and hash-table resizing. The key insight: cheap operations bank credit that funds the rare expensive ones, so worst-case-per-operation pessimism overstates real cost.