The occasionally expensive operation

Why is an operation that sometimes has to copy everything still cheap on average?

Appending to a growable list is supposed to be cheap. Yet the list lives in a fixed block of memory, so sooner or later an append arrives with nowhere to put its value, and the whole thing must be moved into a bigger block. That append copies every element you have ever added.

So here is the puzzle: a million appends, and some of them cost a million steps apiece. Why is the total not catastrophic — and in what sense is it fair to call an operation "cheap" when it demonstrably sometimes is not?

Let us do the arithmetic rather than trust the slogan. Suppose that whenever the block fills, we allocate one twice as large and copy across. Starting from one slot and growing to a million, the copies happen at sizes 1, 2, 4, 8, and so on up to about a million. Add those up. What does a sum of doubling numbers come to?

Just under twice the last one. That is the fact the whole subject rests on: 1 + 2 + 4 + … + n is 2n - 1. So a million appends did at most two million units of copying in total, plus one write each. Divide by the million appends and you get a constant — roughly three units per append, no matter how large the list grows. The expensive operations are rare in exactly the proportion that they are expensive, and the two cancel.

Now test whether the doubling mattered, because this is where intuition usually fails. Suppose instead we grow by a fixed hundred slots each time. Then we resize a million divided by a hundred times, and the copies cost 100, 200, 300, … up to a million. That is an arithmetic series, which sums to about n squared over two hundred — five billion units for a million appends. Same rare-expensive-operation story, catastrophically different total. So the saving is not "expensive things are rare"; it is that the gap between expensive operations grows in step with their cost. Geometric growth does that; additive growth does not.

Now the part that matters more than the arithmetic. What kind of claim have we just made? Not a probabilistic one. Nothing here assumed a distribution over inputs, nothing was averaged over random choices, and there is no unlucky sequence of appends that defeats it. We proved a bound on the total for the worst possible sequence, then divided. That is amortized cost, and it is a worst-case guarantee wearing an average's clothing.

This distinction has teeth. Average-case analysis says "if your input is drawn as I assume, you will usually be fine" — and an adversary who picks your input breaks it. Amortized analysis says "over any n operations, the total is bounded" — and no adversary can do anything about it, because the argument never mentioned the input's shape. A hash table's constant-time lookup is average-case, and hash-flooding attacks exploit that. A growable array's constant-time append is amortized, and there is no corresponding attack.

There is a useful bookkeeping trick that makes the argument feel less like a coincidence. Charge each append three units instead of one: one to write the value, and two saved as credit on the newly written cell. When the block of size n fills, exactly half its cells — the ones added since the last resize — carry unspent credit, two units each, which is precisely the n units the copy will cost. The credits always suffice, so the charge is never a lie. This is the accounting method, and it is the same proof as the sum, told forwards.

Is amortized ever the wrong measure, though? Yes, and it is worth saying plainly. If you are flying an aircraft or filling an audio buffer, the guarantee you need is on the single worst operation, not on the average of a run. Amortized constant time still means one unlucky append stalls for milliseconds while a large array is copied. Real-time systems therefore use deamortized structures that move a few elements on every operation instead of all of them at once, paying a slightly higher constant to eliminate the spike.

Two refinements.

First, the growth factor is a genuine engineering choice, not just two-versus-anything. Any factor above one gives amortized constant appends; the factor only changes the constant and the wasted space. There is a subtler argument for factors below two: with doubling, all previously freed blocks summed together (1 + 2 + … + n/2 = n - 1) are always just too small to hold the next request, so the allocator can never reuse them. A factor nearer 1.5 eventually allows reuse. This is why several implementations chose 1.5; it is a memory-fragmentation argument, not a speed one.

Second, shrinking needs hysteresis. If you halve the array as soon as it is half empty, then a caller alternating append and remove at the boundary triggers a full copy every single time, and the amortized bound collapses to linear per operation. The standard fix is to shrink only at one quarter full, so that after any resize the array is half full and a linear number of operations must occur before the next one.

• The potential method, which generalises the credit trick into a function of the structure's state and is how splay trees and Fibonacci heaps are analysed.
• Deamortization: how to convert an amortized bound into a genuine worst-case one by spreading the rebuild across subsequent operations.
• Why persistent (immutable) structures complicate amortized arguments, since an adversary can replay the expensive operation from the same old version repeatedly.

Every term the collection defines is gathered in the glossary.