I understand the basic idea of amortized complexity, but I'm looking for a clearer theoretical intuition. How can an operation that is occasionally very expensive still have a low amortized cost? What is the cleanest mathematical way to understand this, perhaps using a dynamic array or the accounting and potential methods?
4 Answers
The key is to analyze a whole sequence of operations instead of judging each operation independently. Amortized analysis gives a worst-case bound on the total cost of any sequence, without relying on probability. A rare expensive operation can be paid for by many cheap operations, so the average cost across the sequence stays small.
A dynamic array is the standard example. If the capacity increases by a fixed amount, such as five slots, resizing remains frequent: a constant fraction of insertions can require copying many elements, so the amortized cost is linear. If the capacity doubles, the resizes become increasingly far apart. The total number of elements copied over n insertions is O(n), so the average cost per insertion is O(1), even though an individual resize costs O(n).
The accounting method is a useful way to visualize it. You assign each operation a slightly inflated pretend cost. Cheap operations leave some credit behind, and that stored credit pays for a later expensive operation. For a dynamic array that doubles in size, most insertions are cheap, while a resize copies many elements. The extra charge collected from earlier insertions covers those copies, keeping the amortized insertion cost constant.
The potential method expresses the same idea mathematically. Define a nonnegative potential function Φ(state) representing stored-up work. For an operation, set its amortized cost to actual cost + Φ(after) − Φ(before). Over a sequence, the potential changes telescope, so the total actual cost is bounded by the total amortized cost, assuming the initial potential is zero or otherwise accounted for. For a doubling array, a suitable potential grows with the unused capacity or accumulated elements, and the potential built up by cheap insertions pays for the occasional resize.
The telescoping sum makes the accounting precise. It shows why the potential is not just an analogy—the intermediate credits cancel out, leaving a bound on the entire sequence.
That helps clarify the difference from average-case analysis. The expensive operation is guaranteed to be affordable across the sequence, rather than merely being unlikely.