Amortised cost, and why it is honest

How an occasional expensive operation can still leave every operation cheap on average.

You drink one coffee at home every morning. You do not buy beans daily. Once a month you buy a large bag for twelve pounds, and for the next thirty mornings the coffee costs you nothing extra.

What does a morning coffee cost? Saying "nothing, except one morning a month when it costs twelve pounds" is technically accurate and completely useless. The sensible answer is forty pence a morning: the total divided by the number of mornings. Spreading a lump cost over the things that caused it is called amortising it, and the word is borrowed directly from accounting.

The same idea, in a data structure

A packed run of memory has a fixed size, fixed at the moment you asked for it. The boxes just past the end of your run may belong to another part of the program, so you cannot quietly extend into them. So what happens when you want to add one more item than there is room for?

The usual answer: ask for a new run of memory that is twice as big, copy everything across, release the old one, and then add the new item. That copying is real work, proportional to how many items you already had. Occasionally, then, adding one item is expensive.

Let us count it exactly, starting from an empty collection with room for one item. The number of items a run has room for is called its capacity, so we are starting with a capacity of 1. Adding an item costs 1 step to write it. When there is no room left, we first ask for a run of twice the capacity and copy everything across, and each item copied is 1 step.

Add the last column for the first eight additions: 1 plus 2 plus 3 plus 1 plus 5 plus 1 plus 1 plus 1 gives 15 steps for 8 additions, which is under 2 steps each. Carry on to 16 additions and the total is 31 steps, which is again just under 2 each. The expensive ones are real, and they are getting bigger, but they are also getting rarer at exactly the same rate.

That is the crux. Doubling means the copy of 8 items happens only after 8 cheap additions have gone by, and the copy of 1,000 items only after 1,000 cheap additions. Every expensive operation has already been paid for by the cheap ones that preceded it.

Not the same thing as an average case

These two get confused constantly, and the difference is genuinely important.

An average case rests on an assumption about what your data looks like, and that assumption can turn out to be false or be deliberately broken. An amortised bound rests only on arithmetic about the sequence of operations itself. No input can defeat it, because the input never entered the argument.