Averaging the cost over a sequence of operations, so that a rare expensive step is paid for by the many cheap ones around it — with no probability involved.
Some data structures have an operation that is usually trivial and occasionally enormous. A dynamic array append is normally one write, but when the array fills it copies everything. Bounding each operation by its worst case gives a bound that is correct and wildly pessimistic, because the expensive case cannot happen often. Amortized analysis bounds the average cost per operation over a worst-case sequence. Crucially, it is not probabilistic — there is no averaging over inputs and no expectation. The guarantee holds for every sequence.
A k-bit counter A[0:k-1], initially zero, with an INCREMENT that flips trailing 1s to 0 and then a 0 to 1.
INCREMENT(A, k)
1 i = 0
2 while i < k and A[i] == 1
3 A[i] = 0
4 i = i + 1
5 if i < k
6 A[i] = 1Worst case for one increment: Θ(k), when every bit is 1. Naive bound for n increments: O(nk). That is a large overestimate.
T(n) on the total cost of a sequence of n operations, then says the amortized cost per operation is T(n)/n. Every operation gets the same amortized cost, even if the operations differ in kind.Counter. Count how often each bit flips over n increments. Bit 0 flips every time, bit 1 every other time, bit i every 2ᵢ times. Total flips:
∑ from i=0 to k-1 of ⌊n/2ᵢ⌋ < n · ∑ from i=0 to ∞ of 1/2ᵢ = 2nSo n increments cost O(n), and the amortized cost per increment is O(1), not O(k). The geometric series does the work — the same series that made BUILD-MAX-HEAP linear in Chapter 6.
Stack with MULTIPOP. A stack supporting PUSH, POP, and MULTIPOP(S, k), which pops min(k, |S|) items. A single MULTIPOP costs O(n), so the naive bound for n operations is O(n²). But each object can be popped at most once for each time it is pushed, and there are at most n pushes, so total pops across the whole sequence are at most n. Total cost O(n), amortized O(1) per operation.
Requirement: ∑ amortized costs ≥ ∑ actual costs for every sequence
Equivalently: total credit ≥ 0 at all timesCounter. Charge 2 dollars to set a bit from 0 to 1: one pays for the actual flip, one is left as credit on that bit. Resetting a bit to 0 is charged nothing — it is paid by the credit sitting on it. Each increment sets at most one bit to 1, so it costs at most 2 amortized. Every 1 bit in the counter carries exactly one dollar, so credit is never negative. Amortized cost: O(1).
Stack. Charge 2 for PUSH: one to push, one as credit on the plate. POP and MULTIPOP cost 0 amortized, paid by the credit each plate carries. Since a plate must be pushed before it can be popped, credit never goes negative.
The most powerful and the most mechanical. Instead of credit on individual objects, define a single function of the whole structure’s state.
Φ maps each state Dᵢ of the data structure to a real number Φ(Dᵢ), the potential of that state. The amortized cost of the ith operation isĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁) // actual cost plus change in potential
Total: ∑ĉᵢ = ∑cᵢ + Φ(Dₙ) - Φ(D₀)Φ(Dₙ) ≥ Φ(D₀) for all n, the total amortized cost is an upper bound on the total actual cost. The easy way to guarantee this is to define Φ so that Φ(D₀) = 0 and Φ(Dᵢ) ≥ 0 always. Forgetting to verify non-negativity is the standard error.Counter. Let Φ(Dᵢ) = bᵢ, the number of 1 bits after the ith increment. Suppose that increment resets tᵢ bits to 0. Its actual cost is at most tᵢ + 1. The number of 1 bits changes by at most 1 - tᵢ, so:
ĉᵢ ≤ (tᵢ + 1) + (1 - tᵢ) = 2The tᵢ terms cancel exactly. Since Φ(D₀) = 0 and Φ is always non-negative, the total cost of n increments is O(n). Two lines, and it also handles a counter that does not start at zero — a case aggregate analysis handles less gracefully.
Stack. Let Φ be the number of objects on the stack. PUSH: actual 1, potential +1, amortized 2. POP: actual 1, potential -1, amortized 0. MULTIPOP of k′ items: actual k′, potential -k′, amortized 0.
Φ is the creative step, and the usual choice is “how far the structure is from its cheapest configuration”.The payoff, and the promise made back in Chapter 10.
A table that grows on demand. When an insert finds the table full, allocate a new table of double the size, copy everything over, and free the old one. Define the load factor α = num/size.
TABLE-INSERT(T, x)
1 if T.size == 0
2 allocate T.table with 1 slot; T.size = 1
3 if T.num == T.size // full — expand
4 allocate new-table with 2 · T.size slots
5 insert all items of T.table into new-table // Θ(T.num)
6 free T.table
7 T.table = new-table; T.size = 2 · T.size
8 insert x into T.table
9 T.num = T.num + 1Expansions happen at insertions 1, 2, 3, 5, 9, 17, …, that is at 2ᵢ + 1. Total copying cost over n inserts:
∑ from j=0 to ⌊lg n⌋ of 2ʲ < 2nPlus n for the inserts themselves, giving < 3n. Amortized cost per insert: O(1).
Choose Φ(T) = 2·T.num - T.size. Immediately after an expansion the table is half full, so Φ = 0 — the structure is spent. As inserts accumulate, Φ rises to T.num just as the table fills, which is exactly the copying cost about to be incurred. Working through both cases gives amortized cost 3 either way.
c inserts and total copying would be Θ(n²) — amortized Θ(n) per insert. Doubling is what makes the series geometric. For deletion, the naive rule “halve when the table is half full” is a trap: alternating insert and delete at the boundary triggers a full copy every single time, giving Θ(n) amortized. The fix is hysteresis — contract only when the table drops to one quarter full, so after contracting it is half full and far from either threshold.| Method | How it works | Best when | Limitation |
|---|---|---|---|
| Aggregate | Bound the total for n operations, divide by n | The total is easy to count directly | Every operation gets the same amortized cost |
| Accounting | Prepay, storing credit on specific objects | You can point at what the credit is for | Must design the credit placement |
| Potential | A function of the whole state; the difference pays the excess | Different operations need different amortized costs; the structure has a natural “distance from cheap” | Finding Φ takes insight |
All three always give valid bounds; they are accounting schemes, not different theorems. Different methods can assign different amortized costs to individual operations while agreeing on the total.
n. The binary counter is O(n) for n increments because bit i flips only n/2ᵢ times.ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁). Ensure Φ(D₀) = 0 and Φ ≥ 0 throughout. Think of it as stored energy.O(1) amortized insert. Growing by a fixed increment gives Θ(n).Part V returns to data structures, now with amortized analysis available. Chapter 17 shows how to augment a red-black tree with extra per-node information — subtree sizes, interval endpoints — to get order-statistic and interval trees at no asymptotic cost. Chapter 19’s disjoint-set forests need amortized analysis outright: their near-constant α(n) bound is an amortized one.