Amortized analysis

Averaging cost over a sequence — with no probability

Amortized analysis bounds the average cost per operation over a worst-case sequence of operations. It shows that even if one operation is occasionally expensive, the average over the whole sequence is small. The critical distinction the exam tests:

> Amortized analysis involves no probability and no distribution. It is a worst-case guarantee on the average cost per operation — not an average-case (expected) analysis.

If any sequence of $n$ operations costs at most $T(n)$, the amortized cost per operation is $T(n)/n$, and that holds for every sequence, not just typical ones.

The three methods

1. Aggregate — bound the total cost $T(n)$ of the whole sequence directly, then charge $T(n)/n$ to every operation equally.
2. Accounting — assign each operation a (possibly different) amortized charge ${\hat{c}}_i$; overcharges bank credit on data-structure objects, undercharges spend it. Valid as long as total credit stays $\ge 0$, i.e. $\sum {\hat{c}}_i\ge \sum c_i$.
3. Potential — define a potential $\Phi (D)$ on the data-structure state; the amortized cost is ${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$. By telescoping, $\sum {\hat{c}}_i=\sum c_i+\Phi (D_n)-\Phi (D_0)$, so if $\Phi (D_n)\ge \Phi (D_0)$ the amortized total upper-bounds the actual total.

All three give upper bounds on the same real cost; they only differ in bookkeeping. Pick whichever is most natural.

Warm-ups: the stack with MULTIPOP and the binary counter

MULTIPOP(S, k) pops $\min (s,k)$ items — a single call is $O(n)$, so a naive bound on $n$ operations is $O(n^2)$. But aggregate analysis nails it: each object is pushed at most once and popped at most once, so across the whole sequence there are at most $n$ pops total. Total cost $\le 2n=O(n)$, amortized $O(1)$. The accounting view: charge $\$2$ at each PUSH ($\$1$ to push now, $\$1$ of credit on the object for its eventual pop); then POP and MULTIPOP are $\$0$ amortized. The potential view: $\Phi = $ stack size — PUSH is $1 + 1 = 2$, MULTIPOP of $k'$ items is $k' - k' = 0$.

The $k$-bit binary counter: INCREMENT flips $A[0]$ every time, $A[1]$ every other time, $A[2]$ every fourth time, … So total flips over $n$ increments $={\sum }_i\lfloor n/2^i\rfloor <n{\sum }_{i=0}^{\infty }{2}^{-i}=2n=O(n)$. Amortized $O(1)$ per INCREMENT.

The headline result: dynamic-table doubling

A dynamic table (Python list, Java ArrayList, C++ vector) grows by doubling when it fills. A TABLE-INSERT that triggers a resize costs $\Theta (\text{size})$ (copy everything to a bigger array); a non-resizing insert costs $1$. Naive bound: $O(n^2)$. But resizes happen at sizes $1,2,4,8,\dots$, so the total copy cost over $n$ inserts is $1+2+4+\cdots +n/2<n$ (a geometric series). Total work $<n+n=2n=O(n)$, so insertion is $O(1)$ amortized despite occasional $\Theta (n)$ resizes. (Contraction needs care: halving at $\alpha <1/4$ rather than $\alpha <1/2$ avoids thrashing, where alternating insert/delete triggers a resize every step.)

Worked example — count the copies, see the geometric series

Do $n=16$ appends into a table that starts at capacity 1 and doubles when full. The capacity passes through $1\to 2\to 4\to 8\to 16$, and each doubling copies the existing elements: $1+2+4+8=15$ total copies for 16 appends. That is $15/16=0.9375$ copies per append — less than one copy each on average, even though the single resize from 8 to 16 alone copied 8 elements. The expensive resizes are exactly cancelled by the cheap inserts between them: $O(1)$ amortized, demonstrated, not just asserted.