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

Aggregate — bound the total cost $T(n)$ of the whole sequence directly, then charge $T(n)/n$ to every operation equally.
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$.
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 + \dots + 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.