Amortised Analysis

Push onto a dynamic array a million times and almost every push is trivially cheap — write a value, bump a counter. But every so often the array fills up, and that one unlucky push must allocate a bigger buffer and copy everything across: a \Theta(n) jolt. A worst-case-per-operation analysis screams "O(n) per push!" and concludes a sequence of n pushes costs O(n^2). That bound is true and useless — the real total is \Theta(n), because the expensive pushes are rare enough to pay for.

Amortised analysis is the art of charging each operation its fair share of the total cost of a whole sequence, so that a rare expensive operation is subsidised by the many cheap ones around it. Crucially — and this trips everyone up once — it is not average-case analysis: there are no probabilities, no random inputs, no expectation. The amortised bound is a worst-case guarantee over any sequence of operations. We will meet the three classic techniques: the aggregate, accounting, and potential methods.

Method 1 — the aggregate method

The bluntest instrument, and often enough: bound the total cost T(n) of any sequence of n operations, then declare the amortised cost per operation to be T(n)/n. Every operation is assigned the same amortised cost, regardless of whether it was individually cheap or dear.

A push costs 1 for the write. When the array of capacity c is full, a push first copies c elements into a buffer of size 2c.
Across n pushes, copies happen at sizes 1, 2, 4, \dots, so total copy work is 1 + 2 + 4 + \dots + 2^{\lfloor \log_2 n\rfloor} < 2n.
Total cost T(n) < n + 2n = 3n = \Theta(n), so the amortised cost per push is T(n)/n < 3 = O(1).

The geometric series is the whole secret: doubling makes resizes exponentially rarer as they grow more expensive, and a geometric sum is dominated by its last term. The chart plots the true cumulative cost of n pushes — a staircase with a jump at each resize — hugging the straight line 3n. It never escapes the line: that is the amortised bound, made visible.

Method 2 — the accounting (banker's) method

The aggregate method gives one flat amortised cost; the accounting method is subtler and more flexible. You invent an amortised charge for each operation — usually more than it really costs — and bank the surplus as credit stored on the data structure. Later, an expensive operation pays its true cost by spending the credit that earlier cheap operations left lying around. The only rule you must never break:

Total credit must never go negative. If it stays \ge 0 at all times, then \sum \text{amortised} \ge \sum \text{actual}, so the amortised total is a valid upper bound on the real total.
You may charge different amortised costs to different operation types — the art is choosing charges that keep the bank solvent.

For the dynamic array, charge 3 per push: 1 pays to write the new element, and 2 is saved as credit on that element. When the array later doubles, every element in the old half carries exactly the credit needed to pay for copying itself (and it has been sitting there since the last resize). The bank never runs dry, so amortised O(1) per push — the same 3 the aggregate method found, but now with a story for where the money goes.

Two more classics: the multipop stack and the binary counter

Amortisation shines whenever cheap operations quietly build up a resource that a rare expensive operation then consumes all at once.

class MultiStack { private s: number[] = []; push(x: number): void { this.s.push(x); } // actual cost 1 multipop(k: number): void { // actual cost min(k, size) let n = Math.min(k, this.s.length); while (n-- > 0) this.s.pop(); } }

Multipop stack. A single multipop can cost \Theta(n). But you can only pop an element that was pushed, and each element is pushed once and popped at most once. So over any sequence of n operations the total pop work is \le the total push work \le n. Amortised cost per operation: O(1). (Accounting view: charge 2 per push — one to push, one prepaid credit to cover its eventual pop.)
Binary counter increment. Incrementing a b-bit counter flips the trailing run of 1s to 0 and one 0 to 1. A single increment can flip \Theta(b) bits (e.g. 0111{\to}1000). But bit i flips only once every 2^i increments, so n increments flip n + n/2 + n/4 + \dots < 2n bits total. Amortised \Theta(1) flips per increment. (Accounting view: pay 2 to set a bit to 1 — one to flip it now, one credit banked to pay for clearing it back to 0 later.)

Notice the recurring shape: a geometric series (1+2+4+\dots or n+n/2+n/4+\dots) collapses to a constant times n, and the accounting story is always "prepay for the cleanup when you do the cheap thing."

Suppose that instead of doubling you grew the buffer by a fixed 100 slots each time it filled. Now a resize happens every 100 pushes and copies \Theta(n) elements, so the total copy work over n pushes is 100 + 200 + \dots + n \approx n^2/200 = \Theta(n^2) — amortised \Theta(n) per push, catastrophic. The magic of multiplicative growth is that it makes resizes geometrically rare relative to their cost; any growth factor >1 (1.5×, as many real implementations use, works fine) gives amortised O(1). Additive growth cannot, no matter how large the chunk. The factor is a space–time knob: a smaller factor wastes less memory but resizes more often.

The single most common error is to hear "amortised O(1)" as "usually O(1), on average". It is stronger and completely different. There is no randomness anywhere: the amortised bound holds for the worst possible sequence of operations an adversary can devise. It is an accounting identity, not an expectation. This also means a single operation can still be genuinely slow — an individual push really can cost \Theta(n) — which matters for real-time systems where a latency spike is unacceptable even if the throughput is fine. "Amortised O(1)" promises the total over any sequence is O(n); it promises nothing about the cost of the one operation you happen to be waiting on.