Amortized Analysis

why per-operation worst case overcounts

Suppose you want to bound how long a whole program runs when it calls one data-structure operation many times. The lazy way is to find the single most expensive that operation can ever be, then multiply by the number of calls. This is always a valid upper bound — but it can be hugely too pessimistic, because it pretends every call hits the worst case at once, which is often impossible.

Here is the trap in concrete terms. A dynamic array's append is usually O(1), but occasionally it must copy all n existing elements, so its single-operation worst case is O(n). Multiply that O(n) worst case by n appends and you get an O(n^2) bound for n appends. Yet the expensive copies cannot all be expensive at the same time: a copy of n elements only happens after roughly n cheap appends have grown the array to size n, so the costly steps are spread out. Counting them honestly gives O(n) total, not O(n^2). The per-operation bound overcounted by a whole factor of n because it ignored the fact that one operation's high cost forces the next many operations to be cheap.

Recognizing this overcount is the whole motivation for amortized analysis. Whenever expensive operations are rare and must be 'earned' by many cheap ones — array resizing, incrementing a binary counter, splay-tree restructuring — the product of worst-case-per-operation and number-of-operations is loose, sometimes by large factors. The honest caveat in the other direction: sometimes the per-operation worst case really IS tight (every operation can independently be expensive), and then amortized analysis buys you nothing. You have to check that the expensive operations genuinely constrain one another before you expect amortization to help.

Multipop stack: a single Multipop can pop k items, and k can be as large as the current stack size, so its per-operation worst case is O(n). Multiplying O(n) by m operations gives a loose O(n*m) bound. But you can only pop an item once after it was pushed once, so all the pops together cost no more than all the pushes — the honest total over m operations is O(m), not O(n*m).

Worst-case-per-operation times count is a valid but often loose upper bound; amortized analysis tightens it.

The product bound is never wrong, only sometimes loose. Amortized analysis is worth doing only when expensive operations are rare and constrained; if each operation can independently hit its worst case, the simple product is already tight.

Also called
per-operation overcounting逐操作高估