11 min read

Worst case, amortised, expected: three different promises

All three get quoted as though they were the same guarantee. They are not, and the difference decides whether a system misses a deadline.

A photo album holds a fixed number of pages. When it fills up, the shop rebinds it into an album with twice as many pages, which means copying every photo already in it. Adding a photo is normally instant and occasionally involves copying the lot.

That is exactly how a growable array behaves, and it is the standard example of a cost that is expensive now and then and cheap on average in a way you can actually rely on. Run the sequence and watch the two columns on the right.

Sixteen appends, and what each one costPython

Change the 17 to 65 and run it again. The last column keeps hovering below 2 however long the sequence gets.

One append in the sequence copied 8 cells and another copied 4, so the worst single append is not cheap and gets worse as the album grows. The running average never passes 2. Both facts are true at once and they support completely different promises.

Amortised cost

The copying happens at counts 1, 2, 4, 8 and so on, and copies that many cells each time. Over $n$ appends the total copied is at most $1 + 2 + 4 + \cdots + 2^k$ where $2^k < n$ . That sum is $2^{k+1} - 1$ , which is less than $2n$ , so the total work for $n$ appends is under $2n$ copies plus $n$ writes.

1 + 2 + 4 + \cdots + 2^{k} \;=\; 2^{k+1} - 1 \;<\; 2n \qquad \text{whenever } 2^{k} < n

Each rebinding costs twice the one before, so the last one alone is worth more than all the earlier ones together.

The amortised cost of an operation is the worst-case total cost of a sequence of $m$ operations, divided by $m$ . Here the total for $n$ appends is under $3n$ units, so the amortised cost per append is under 3, that is $\Theta(1)$ , even though one individual append costs $\Theta(n)$ .

Expected cost

A different kind of claim arises when the algorithm itself flips coins. Take the left-to-right search from earlier and change one thing: instead of examining positions in order, examine them in a random order chosen fresh on each run. Now run it twenty thousand times on the input a left-to-right scan handles worst, the one whose target sits at the very end.

The worst input, searched in a random orderPython

Change the target to 14, the entry a left-to-right scan finds first, and run it again. The average barely moves, which is the whole point.

The average lands near 3.5, which is $(n+1)/2$ for $n = 6$ , and the worst trial seen is 6. The expected cost is the mean over the algorithm's own random choices, for a fixed input, and then the worst such mean over all inputs. Nothing was assumed about where the data came from, because the randomness is supplied by the algorithm rather than by the world.

That is the difference from an average-case claim. Average case says: if inputs arrive from this distribution, the mean cost is this. Someone sending you sorted data, or an attacker choosing inputs on purpose, can make that claim worthless. An expected-cost claim survives both, because the adversary does not get to see the coins.

Claim	Promise	What can break it	Typical wording
Worst case	Every operation on every input costs at most this	Nothing, once proved	runs in O(n log n)
Amortised	Any sequence of m operations costs at most m times this in total	Nothing, but one operation in the sequence may be slow	amortised O(1) per append
Expected	For every input, the mean over the algorithm's coin flips is this	Bad luck on one run, with probability that shrinks fast	expected O(n log n)
Average case	The mean over inputs drawn from a stated distribution is this	Real data not matching the distribution, or an adversary	O(n) on uniformly random input

What each claim actually promises, and what breaks it.

Where the difference bites

A program generating audio has 5 milliseconds to fill the next buffer, every time, or the listener hears a click. An amortised guarantee is no help there: the one append that copies a million cells lands inside some buffer, and that buffer misses its deadline however good the average was. Such systems need a worst-case bound per operation, and will accept a worse average to get one.

A web service serving a million requests an hour is in the opposite position. The occasional slow request is absorbed, and the total throughput is what matters, so an amortised or expected bound is exactly the right thing to buy. Notice that neither system is choosing the faster algorithm; each is choosing the kind of promise its failure mode requires.

Someone says looking a key up in a hash table is O(1). Which of the four claims is that, and what would a careful version of the sentence say?

It is an expected-cost claim, or an average-case one depending on how the table is built. The worst case for a single lookup is Theta(n), because every key can collide into one bucket. A careful version says: expected O(1) per lookup, when the hash function is chosen at random from a suitable family and independently of the keys. The distinction matters in practice: a service whose hash function is fixed and public has been attacked by feeding it keys that all collide, turning every lookup into a linear scan.

Check yourself

A structure supports an operation with amortised cost O(1) and worst-case cost O(n) for a single operation. Which use is unsafe?

A control loop that must respond within a fixed time on every single callA batch job that performs a million such operations and reports when it is doneA build tool where the total time for the whole run is what is measuredA background indexer with no per-operation deadline