Amortized Analysis

Aggregate, accounting, and potential methods on the dynamic array.

The idea

Amortized analysis answers one question about a data structure: over a worst-case sequence of $n$ operations, what is the average cost per operation? No probability is involved: the average runs across the sequence, not over random inputs. The question matters when most operations are cheap and a few are expensive, since a per-operation worst-case bound then reports only the expensive case and overstates the total.

Write $T(n)$ for the total cost of the whole sequence. The amortized cost per operation is $T(n)/n$, and three standard methods bound it.

The aggregate method bounds $T(n)$ directly and divides by $n$.

The accounting method charges every operation the same fixed amount, more than a cheap operation actually costs. The surplus is stored as credit on the structure and spent later on the expensive operations. The charge is valid as long as the stored credit never goes negative, since then the total charged is at least the total actually spent.

The potential method keeps the same books globally rather than item by item. A potential function $\Phi$ assigns each state of the structure a number, the work saved up in it, and the amortized cost of an operation with actual cost $c$ is $\hat{c} = c + \Delta\Phi.$ Summed over the sequence this telescopes to $T(n)$ plus the net change in $\Phi$, so if $\Phi$ never falls below its starting value, the amortized costs bound the true total. A good $\Phi$ rises during cheap operations by just enough to fall and pay for an expensive one.

Ways to work on it

• Walkthrough. Aggregate, accounting, and potential methods on a doubling array.
• Practice. Aggregate-method total cost for a sequence of doubling pushes.
• Hardest. Potential method: amortize the expensive doubling push to O(1).

Not sure where to start? Take the ten-question placement test.