I understand the basic idea of amortized complexity, but I'm looking for a clearer theoretical explanation of why an operation that is occasionally very expensive can still have a low amortized cost. What is the cleanest way to understand this mathematically, especially for examples like resizing a dynamic array?
3 Answers
The accounting method gives a useful intuition: 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 cost constant time, while a resize copies many elements. Since the number of elements copied over all resizes is a geometric sum, the total work for m insertions is O(m), giving O(1) amortized time per insertion.
The key is to analyze the total cost of a whole sequence rather than judging every operation separately. If a sequence of m operations costs at most O(mf(n)) overall, then the average—or amortized—cost per operation is O(f(n)). The occasional expensive operation is paid for by the many cheap operations around it. This is a worst-case guarantee over sequences, not a probability-based average-case claim.
The potential method is the cleanest formal version. Choose a nonnegative potential function Φ(state) representing saved-up work, then define the amortized cost of an operation as actual cost plus the change in potential: amortized cost = actual cost + Φ(after) − Φ(before). When you sum this over a sequence, the potential changes telescope, and the final potential cannot be negative. For a doubling array, a suitable potential grows as unused capacity is consumed, then drops enough during a resize to pay for copying the elements. This proves every insertion has O(1) amortized cost. It’s also important not to confuse this with average-case analysis: amortized analysis does not assume random inputs or probabilities.
The distinction from average-case analysis helps a lot. The potential function shows exactly where the credit is stored and why the expensive operation is covered without relying on randomness.
That makes sense—the important point is that the guarantee applies to the entire sequence, rather than to each individual operation.