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.

What breaks the accounting #

Both proofs above share an assumption so basic that neither states it: each state of the array is used once. The credit attached to an element is spent on one future copy, because there is only one future.

That assumption is not a technicality, and there is a common use that violates it.

Suppose the array is persistent — a snapshot is kept, as an undo point, as a version in a copy-on-write structure, or simply because a reference was handed to somebody who kept it. Now take a full array of 1,024 elements and append to it twice, each time starting from the same saved state. Both appends find a full array. Both trigger a copy of 1,024 elements. The credit that 1,024 appends built up has been spent twice, and nothing was double-charged to pay for it.

Do that $k$ times from the same saved state and the cost is $k \times 1{,}024$ copies. For comparison, building the whole 1,024-element array from empty costs $1 + 2 + 4 + \cdots + 1{,}024 = 2{,}047$ copies in total. Two appends from the saved state cost as much as the entire construction. A hundred of them cost fifty times it.

The amortised bound has not become a weaker bound; it has stopped applying. It is a statement about a sequence of operations, and branching from a saved state turns the sequence into a tree. Every credit in the accounting method is claimed by one path; a tree has many paths and each of them claims the same credit.

This is exactly why persistent data structures are built differently. A persistent vector is a shallow tree of small blocks rather than one flat buffer, so appending copies a path of length $\log n$ rather than the whole array, and the cost of an append is the same whichever version it starts from. That is a genuinely worse constant for the ordinary linear case — every access walks a few levels rather than indexing directly — bought in exchange for a bound that survives branching.

The general lesson is the one this essay keeps arriving at from different directions. An amortised bound is a claim with a quantifier in it, and the quantifier is over sequences. Read as a claim about operations it is false in the sawtooth. Read as a claim about any usage it is false here. Both failures come from dropping the same word.

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.

The amortised cost is a sawtooth too, and the sweep cannot see it #

Four significant figures of agreement across a factor of sixty-four is a striking table, and the striking part is an artefact of which sizes were chosen.

The arithmetic is exact. Doubling from capacity one, the copies happen at $1, 2, 4, \ldots, 2^k$ for the largest $2^k < n$, so the total copying is $2^{k+1} - 1$ and the cost per append is

$$1 + \frac{2^{k+1} - 1}{n}.$$

At $n = 1{,}000$ the largest power below is 512, so the copies total 1,023 and the cost is $1 + 1023/1000 = 2.023$. At 4,000: 4,095 over 4,000, or 2.024. At 16,000 and 64,000 the same, to the digit. Every row of the table recovered from the formula with nothing fitted.

Now look at what the formula does between those points. The numerator $2^{k+1}$ is somewhere between $n$ and $2n$, so the amortised cost oscillates between 2 and 3 as $n$ moves through a power of two — just after a resize it is nearly 3, just before the next one it is nearly 2. It does not converge to anything; it is a sawtooth in $\log n$, exactly like the per-operation costs it is an average of, one level up.

The table shows a constant because its four sizes are 1,000 and three quadruplings of it, and quadrupling does not change where a number sits between consecutive powers of two. The fractional parts of $\log_2 n$ are 9.966, 11.966, 13.966 and 15.966 — the same phase of the sawtooth, sampled four times.

That has a consequence for the check. The gate requires the largest and smallest of these to stay within a factor of 1.35, and the true range of the quantity is 3/2 = 1.5. A sweep at 1,000 and 1,030 would give 2.023 and 2.988, a ratio of 1.48, and the gate would fail on a correct implementation. It passes because every size in it is a power-of-two multiple of the first, which is the natural way to choose a sweep and is the one arrangement that cannot see the effect.

None of which touches the bound. The cost is between 2 and 3 at every $n$, both are constants, and $O(1)$ amortised is exactly right. What is wrong is the reading the table invites — that the per-append cost settles on a value — and the correct statement is that it stays inside a band of width one whose position depends on how recently the array grew.

Which is this essay’s own thesis arriving one level further up, and the neatest possible illustration of it. The sawtooth was smoothed away by averaging over the sequence; averaging over the sequence leaves a smaller sawtooth in $n$; and a sweep that quadruples samples it at one phase and reports a constant. A parameter that waits for another is the general form — a measurement taken at the one setting where the effect is switched off — and choosing a growth factor is where the same band, at other factors, is the whole subject.

Both dials that produce the sawtooth are worth turning, because the amortised cost is a mean over the sequence and a mean can be moved two ways.

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.