Amortized Analysis

Some data structures have an operation that is usually trivial and occasionally enormous. Appending to a dynamic array normally writes one slot, but when the buffer fills it allocates a bigger one and copies everything across. Quoting the worst case for that operation gives O(n), which is technically correct and deeply misleading — it suggests that building a list of a million items costs a trillion operations, when it actually costs about two million.

Amortized analysis measures the average cost per operation across a worst-case sequence of operations.Instead of asking "how bad can one append be?", it asks "how bad can n appends be, in total?" — and then divides. When the expensive cases are structurally guaranteed to be rare, that average is the honest number.

A dynamic array keeps a buffer with some capacity. Appending writes one element; if the buffer is full, it first allocates one of double the capacity and copies every existing element across:

function append(arr, value) {
  if (arr.size === arr.capacity) {
    const bigger = new Array(arr.capacity * 2);   // Θ(n) work,
    for (let i = 0; i < arr.size; i++) {          // but only when full
      bigger[i] = arr.buffer[i];
    }
    arr.buffer = bigger;
    arr.capacity *= 2;
  }

  arr.buffer[arr.size] = value;                   // Θ(1) the rest of the time
  arr.size++;
}

The picture contains the entire argument. The spikes double in height — but they also double in spacing. Each resize is twice as expensive as the last and happens half as often, and those two effects cancel exactly.

The simplest method: add up the cost of the whole sequence, then divide by the number of operations. For n appends, the writes cost n, and the copies happen at sizes 1, 2, 4, 8, … up to n:

Running this for real confirms it: the total cost of n appends divided by n settles at about 2.05 and stays there, whether n is a thousand or a million. The bound of 3 is comfortable, and the important point is that it is a constant — it does not creep upward with n.

A second classic. Incrementing a binary counter flips a trailing run of 1s to 0 and then one 0 to 1, so a single increment can flip Θ(log n) bits. Watch what actually happens over a sequence:

After 8 increments only 15 bits have flipped, not 8 × 4. The reason is visible in the table: bit 0 flips every time, bit 1 flips every second increment, bit 2 every fourth, and so on:

Measured over 100,000 increments, the ratio is 1.99998 flips per increment — converging on 2 exactly as the series predicts.

Also called the banker's method. You invent a charge for each operation — its amortized cost — which may be more or less than what the operation really costs. The surplus is stored as credit on the data structure and later spent on expensive operations.

One rule makes the method valid: the credit balance must never go negative. If it never does, the total amount charged is an upper bound on the total real cost, which is exactly what an amortized bound claims.

For the dynamic array, charge 3 units per append and spend them as:

• 1 unit pays for writing this element into the buffer — spent immediately.
• 1 unit is banked to pay for copying this element at the next resize.
• 1 unit is banked to pay for copying one older element — specifically, one of the elements that were already present at the last resize and so have no credit of their own.

When a resize of a size-n buffer happens, the n elements to be copied are covered: the n/2 elements added since the last resize carry 2 units each, which is enough for themselves and for one older element apiece. The balance never goes negative, so append is O(1) amortized.

The method's advantage over aggregate analysis is that different operations can carry different charges. For a stack supporting push, pop and multipop(k), charge 2 for a push (1 to push, 1 banked for the eventual pop) and 0 for pop and multipop. Every pop is then paid for by the credit its push left behind — so even a multipop that removes a thousand elements is free, because those thousand pushes already paid.

The physicist's method, and the most powerful of the three. Instead of tracking credit on individual elements, define a potential function Φ that maps the whole state of the data structure to a number — the stored-up work it represents.

Summed over a sequence, the Φ terms telescope: every intermediate value appears once positive and once negative, leaving only Φ(end) − Φ(start). So as long as Φ never drops below its starting value — usually arranged by setting Φ(D₀) = 0 and keeping Φ ≥ 0 — the total amortized cost is an upper bound on the total real cost.

Binary counter. Let Φ be the number of 1 bits. An increment that flips k trailing 1s to 0 and one 0 to 1 has actual cost k + 1, and changes the bit count by 1 − k:

The k vanishing is the whole trick. An expensive increment is expensive precisely because it destroys many 1 bits, and destroying them releases exactly the potential needed to pay for the work.

Dynamic array. Let Φ = 2·size − capacity. Immediately after a resize, size is half of capacity so Φ = 0; as appends fill the buffer, Φ climbs to equal capacity by the time the next resize is due — having accumulated precisely enough potential to fund the copy. Working through both cases gives an amortized cost of 3 per append, agreeing with the accounting method.

All three are provably equivalent in power — any bound one can establish, the others can too. Aggregate analysis is the one to reach for when every operation is the same kind. The accounting method suits structures with several operation types. The potential method is the standard choice for anything genuinely difficult, because once Φ is chosen the rest is mechanical.

These two are constantly conflated, and the distinction matters:

• Average-case analysis assumes a probability distribution over inputs.
  • Quick sort is O(n log n) on average because we assume the pivot is usually reasonable. An unlucky input still costs O(n²).
• Amortized analysis assumes nothing and involves no probability.
  • It is a worst-case guarantee about a whole sequence. No adversary can construct an input that makes n appends cost more than O(n) in total.
• The guarantee is about the sequence, not any single operation.
  • One individual append genuinely can cost Θ(n). Amortized analysis never claims otherwise — it claims those expensive operations cannot happen often.

Union-Find is the most striking entry. With union by rank and path compression, a sequence of m operations costs O(m·α(n)), where α is the inverse Ackermann function — a function that grows so slowly it is below 5 for any n that could be written down in this universe. The per-operation worst case is still logarithmic; only the amortized analysis reveals that the structure is effectively constant-time.

Amortized analysis answers "how much work in total?". Some systems need to ask "how long will this onecall take?", and for them the average is the wrong statistic:

• Real-time and safety-critical systems.
  • A pacemaker or an anti-lock braking controller cannot accept one operation taking 100× longer, even if the average is excellent. These systems need worst-case-per-operation bounds.
• Interactive latency and tail percentiles.
  • A resize that stalls one request in a thousand shows up as a p99 latency spike. The amortized average is genuinely O(1) and the user experience is still bad.
• Short sequences.
  • The guarantee is about long runs. If you perform three operations and one of them triggers a resize, the amortized bound has not had room to pay off.

The engineering response is not to abandon the structure but to spread the cost deliberately — incremental or background resizing, or preallocating capacity up front when the final size is known. Both convert a rare large stall into a small predictable overhead on every operation.

• Confusing amortized with average-case.
  • Average-case involves probability over inputs. Amortized is a deterministic worst-case bound on a sequence, with no randomness anywhere.
• Saying "append is O(1)" without qualification.
  • A single append is O(n) in the worst case. The correct phrasing is O(1) amortized, and dropping the qualifier is exactly what confuses people who then see a latency spike.
• Letting credit go negative in the accounting method.
  • The proof only works if the balance is non-negative at every point in the sequence. Verifying that is the actual work of the method.
• Choosing a potential function that can decrease below its start.
  • Φ must satisfy Φ(Dᵢ) ≥ Φ(D₀) for all i, usually arranged by making Φ(D₀) = 0 and Φ non-negative. Otherwise the telescoping sum does not bound the real cost.
• Assuming growth by a constant amount works too.
  • Growing a array by adding 10 slots instead of doubling makes n appends cost Θ(n²) in total. Only geometric growth gives O(1) amortized.

• Amortized cost is the average per operation over a worst-case sequence — not over a distribution of inputs.
• It applies when expensive operations are structurally rare, such as a resize that doubles in cost but halves in frequency.
• Aggregate analysis divides the total by n; the accounting method banks credit; the potential method tracks a function Φ.
• The accounting method requires credit to stay non-negative; the potential method requires Φ never to fall below its starting value.
• Geometric growth is what creates the guarantee — growing by a fixed amount gives Θ(n) amortized, not O(1).
• An amortized bound says nothing about any single operation, so it is the wrong tool for real-time or tail-latency requirements.