What amortised means

A dynamic array — a list, a vector, a slice, whatever a given language calls the thing that grows — supports appending in $O(1)$ amortised time.

That statement is true, it is proved, and it is routinely repeated in a way that suggests appending costs about the same every time. It does not. Appending 512 elements to an array that doubles when full costs one unit for 503 of them and 257 units for one of them.

The word doing the work is amortised, and what it means is: averaged over the sequence. It is a claim about the total, divided by the number of operations. It says nothing whatsoever about any individual operation, and the individual operations are wildly different.

The cost model, stated #

An amortised cost is only meaningful against a stated cost model, so here is this site’s.

Appending costs one unit for the write, plus, if the array was full, the current size for copying every existing element into the new allocation.

That model gives 2.00 units per append averaged over 512 appends, and 2.02 averaged over 64,000. Both are constant under any reasonable definition.

A different and equally defensible model also charges for the write of each element into the new array, giving a factor of two on the copy, and produces the figure of 3 that textbooks usually quote. Neither is more correct. They differ in whether a copy is one operation or two, which is a question about the machine and not about the algorithm.

The point of stating this is that an amortised cost quoted without its cost model is not checkable, and the difference between 2.02 and 3 is entirely a difference of model rather than of measurement. Anyone comparing this page’s number against a textbook’s should compare the models first.

Why doubling gives a constant #

The argument is a geometric series and it is short.

Starting from capacity 1 and doubling, the copies happen at sizes 1, 2, 4, 8, …, up to the largest power of two below $n$. The total copying is

$$1 + 2 + 4 + \cdots + 2^k < 2^{k+1} \le 2n$$

so the total work is at most $n$ writes plus $2n$ copies, which is $3n$ under one model and about $2n$ under this site’s. Divided by $n$ appends, that is a constant.

The essential feature is that the copies get exponentially rarer as they get more expensive, and the two effects exactly cancel. That cancellation is what makes the bound constant rather than merely small, and it is what fails if the array grows by a fixed amount instead — growing by a fixed step is quadratic, and the site’s gate asserts that the amortised-constant check refuses it.

The gate requires the spikes #

There is a second assertion here that is easy to overlook and is the more interesting one.

The site checks that the amortised cost is constant. It also checks that the individual costs are not: the most expensive single append out of 8,192 must cost more than a quarter of $n$. Measured, it costs 4,097 — half the array.

The reason for the second check is that if no individual append were expensive, the word amortised would be distinguishing nothing. A structure whose every operation costs 2 units is $O(1)$ worst case, which is a strictly stronger property — the same relationship that a proved floor has to a measured average, where the stronger statement is the one that admits no exceptions, and calling it amortised would be underselling it. The word only earns its place when there is a gap between the average and the worst, and the gap here is a factor of 2,000.

That pair of assertions is the same shape as several others on this site: a tolerance is only defensible when bracketed by two measured things, and a distinction is only real when both sides of it have been checked.

Where the distinction bites #

Amortised and worst case are the same for most purposes and violently different for a few, and knowing which situation applies is the practical content of this essay.

It does not matter when a million elements are being appended in a loop and the total is what counts. The amortised bound is exactly the right tool: the total is the quantity being measured, and it is linear.

It matters enormously in any system with a latency requirement. A real-time audio callback that must complete in 5 milliseconds cannot afford an append that copies a 100-megabyte array, however rare. The average is irrelevant; the maximum is the specification. The same applies to interactive frame budgets, to network servers with tail-latency targets, and to anything where a percentile rather than a mean is the metric.

For those situations the answer is not a dynamic array, any more than an average-case sorting bound is a latency budget. It is a structure with a genuine worst-case bound — a chunked list, a deque of fixed-size blocks, or an incrementally-resized array that copies a few elements on every operation rather than all of them at once. Each pays something in average throughput to remove the spike.

This is the same tension as an average concealing a tail, one level down, and the resolution is the same: the summary statistic should match the question being asked.

The potential-function proof, and what the picture adds #

The standard proof is not the geometric series. It is a potential-function argument, and it is more powerful because it generalises.

Define the potential of the array as $\Phi = 2 \cdot \text{size} - \text{capacity}$. An ordinary append costs 1 and raises the potential by 2, for an amortised cost of 3. An append that triggers a copy costs $1 + \text{size}$, and the potential drops from $\text{size}$ to $2\cdot\text{size} - 2\cdot\text{size} = 0$… and the arithmetic works out to a constant again.

The technique is genuinely elegant and it is how amortised bounds are proved for structures where no simple summation exists — splay trees, Fibonacci heaps, union-find with path compression.

What it does not do is show the sawtooth. The potential function’s whole purpose is to smooth the spikes away so the algebra is tractable, and having smoothed them it never mentions them again. Somebody who learns the bound from the proof learns a correct statement and does not learn that a single append can cost half the array.

That is the argument for drawing the picture: the proof and the picture say the same thing and leave different impressions, and the impression the proof leaves is the one that gets people into trouble in a latency-sensitive system.

The banker’s view #

There is a third way to prove these bounds, and it is the one most people find easiest to hold.

Charge each append three units instead of one. One pays for the write. The other two go into a savings account attached to that element. When the array fills and has to be copied, every element that must be moved has two units saved — enough to pay for its own move and to leave the newly-doubled half of the array with credit for the next round.

The accounting works because between one resize and the next, exactly as many elements are appended as need to be copied at the next resize. The saved-up credit always covers the bill.

This is the accounting method, and it is equivalent to the potential function — the total credit outstanding is the potential — but it makes the mechanism visible in a way the algebra does not. It also makes the answer to “why three?” concrete: three is the charge that happens to balance the books under a cost model where a copy is one unit. Under this site’s model the measured figure is 2.02, and the difference is entirely in whether the copy’s write is charged separately.

Both methods share the property this essay is about: they establish a fact about the total and say nothing about any individual operation, because smoothing the individual operations away is the technique.

The measurement across sizes #

An amortised bound claims the cost per operation does not drift as the structure grows, and that is checkable directly.

Four significant figures of agreement across a factor of 64 in $n$, and the resize count growing by exactly 2 each time $n$ quadruples — which is $\log_2$ behaving. The site’s gate requires the ratio between the largest and smallest of these to stay under 1.35, so a drift would fail rather than be quietly reported.

That check would catch a real bug. An implementation that grew by a fixed amount rather than a factor would still work, would still be $O(1)$ per append for small $n$, and would show its true quadratic nature only as $n$ got large — exactly the failure mode that a single-size measurement misses and a sweep catches.

Where else the word appears #

Dynamic arrays are the gentlest example. The technique earns its keep on structures where no simple summation would work, and it is worth naming a few so the pattern is recognisable.

Union-find with path compression. A sequence of $m$ operations on $n$ elements costs $O(m \cdot \alpha(n))$, where $\alpha$ is the inverse Ackermann function and is at most 4 for any $n$ that fits in the universe. Individual operations can cost $\Theta(\log n)$; the amortised cost is effectively constant, and the proof is one of the more remarkable potential-function arguments in the subject.

Splay trees. Every operation is $O(\log n)$ amortised and individual operations can be $\Theta(n)$. The structure has no balance invariant at all — it simply rotates the accessed node to the root — and the amortised bound is the only thing keeping it honest.

Fibonacci heaps. Decrease-key is $O(1)$ amortised, which is what makes Dijkstra’s algorithm $O(E + V\log V)$. Individual decrease-key operations can trigger a cascade of cuts costing $\Theta(\log n)$.

In every case the shape is the same: cheap operations bank credit, expensive ones spend it, and the accounting works out. And in every case the individual worst case is much worse than the amortised cost, so the latency objection applies to all of them.

That is why Fibonacci heaps are famous and rarely used. The amortised bound is real, the constants are large, and the spikes are genuine — for most workloads a simpler heap with worse asymptotics wins on both counts.

Three kinds of average #

It is worth separating three words that all mean “not the worst case” and mean quite different things.

Amortised. Averaged over a sequence of operations, with no randomness anywhere. Which is also why the growth factor is a pure constant-factor question — every factor above 1 gives the same class, so the choice lives entirely in the number this essay measures. A worst-case guarantee about the total. Deterministic: the same sequence always costs the same, and there is no input an adversary can choose to break it.

Expected. Averaged over randomness, either in the input distribution or in the algorithm’s own coin flips. Quicksort with a random pivot is expected $\Theta(n \log n)$, meaning it is that on average over the coins, and a very unlucky run is worse.

Average case. Averaged over an assumed input distribution. Weaker than both, because it depends on an assumption about the data that the user of the algorithm may not satisfy.

A dynamic array’s append is amortised, which is the strongest of the three: no distribution is assumed and no randomness is involved. An adversary who chooses the entire sequence of operations still cannot make the total worse than linear. That is a much better guarantee than “expected”, and the shared word “average” hides the difference.