Amortized Analysis

The intuition: cheap pays for expensive

Push an element onto a dynamic array — a vector in C++, an ArrayList in Java, a Python list, a Go slice. Almost every push just writes one slot and bumps a counter: O(1). But occasionally the backing array is full, and the push has to allocate a bigger block, copy every existing element across, and free the old block. That copy is O(n). So is push O(1) or O(n)?

Worst-case-per-operation analysis answers O(n) and walks away — technically true, badly misleading. If you push a million elements, you do not pay a million O(n) copies. You pay a handful of copies, and the rest are dirt cheap. The honest question isn't "how bad is the worst single push?" but "how much does a whole sequence of pushes cost, divided by the number of pushes?" That average is the amortized cost, and for a doubling array it's a flat O(1).

The mental model that makes it click: every cheap push secretly overpays by a constant amount, dropping spare coins into a jar. When the rare expensive copy arrives, the jar already holds exactly enough to pay for it. No operation is ever charged more than a constant, yet the expensive ones are always covered. That's amortization — not a probabilistic average over lucky inputs, but a deterministic accounting over the worst-case sequence.

The mechanism: geometric growth

The magic ingredient is that the array grows geometrically, not by a fixed amount. When it fills, capacity doubles (or grows by 1.5×, or by any constant factor > 1). Suppose you start at capacity 1 and push n elements. Resizes fire at sizes 1, 2, 4, 8, …, up to the largest power of two below n. The copy work summed over all resizes is:

1 + 2 + 4 + 8 + ... + n  =  2n − 1  <  2n

That is a geometric series, and a geometric series that doubles is dominated by its last term — the total is less than twice the final size. So the total copy work across all n pushes is below 2n, which is O(n). Add the n cheap writes (one per push, another O(n)) and the whole sequence costs under 3n operations. Divide by n pushes:

amortized cost per push  =  (total work) / n  <  3n / n  =  3  =  O(1)

The number of resizes over n pushes is ⌈log₂ n⌉ — for a million elements, just 20 resizes total. Each is expensive, but there are vanishingly few of them, and the cheap pushes between them have already banked the cost. This is the aggregate method: bound the whole sequence, then divide.

The three methods, made precise

Robert Tarjan formalized amortized analysis in his 1985 paper Amortized Computational Complexity, unifying three techniques that had floated around the field. All three prove the same O(1)-per-push bound for the doubling array; they differ in how you set up the bookkeeping.

1. Aggregate method. Compute the total cost T(n) of any sequence of n operations and call the amortized cost T(n)/n. We just did this: T(n) < 3n, so amortized cost < 3. Simple, but it gives every operation the same amortized cost — no good when different operations should be charged differently.

2. Accounting (banker's) method. Assign each operation an amortized charge that may differ from its real cost. Overcharges accumulate as credit stored on specific elements of the structure; undercharges spend that credit. The rule: stored credit must never go negative. For the doubling array, charge each push 3 units. One unit pays for writing the element. The other two are stored on it. When a resize copies n elements, each of the n/2 newest elements still carries 2 credits — exactly enough to pay to move itself and one older element that has already spent its credit. The credit invariant holds, so amortized push is 3 = O(1).

3. Potential method. Define a potential function Φ mapping each data-structure state to a non-negative number — think of it as stored energy. The amortized cost of an operation is its actual cost plus the change in potential:

amortized(op)  =  actual(op)  +  Φ(after)  −  Φ(before)

For the doubling array, set Φ = 2·size − capacity. A normal push raises size by 1 (Φ goes up by 2) and costs 1, so its amortized cost is 1 + 2 = 3. A resize at a full array (size = capacity = m) copies m elements (actual cost m+1), then capacity doubles to 2m: Φ drops from 2m − m = m to 2(m+1) − 2m = 2, a change of (2 − m). Amortized cost = (m+1) + (2 − m) = 3. Every push, cheap or expensive, has amortized cost 3 — and because Φ starts at 0 on the empty table and never drops below that starting value (Φ ≥ 0 throughout), the sum of amortized costs upper-bounds the real total. O(1) again.

The potential method is the workhorse for hard proofs (Fibonacci heaps, splay trees, union-find) because Φ packages "how much trouble is the structure storing up" into a single number you can reason about locally.

When amortized analysis is the right lens

• A rare operation dominates the worst case but happens infrequently. Table doubling, hash-table rehashing, splay-tree rotations — the per-op worst case is misleadingly bad.
• The structure's state changes the cost of future operations. A union-find that flattens paths makes later finds cheaper; that earned cheapness is exactly what amortization captures.
• You only care about total throughput, not individual latency. Batch jobs, compilers, offline processing — nobody times one push.

And when it's the wrong lens: real-time systems where every single operation must finish within a deadline. An amortized-O(1) push that occasionally blocks for O(n) to copy a 10-million-element array is unacceptable in an audio thread, a robotics control loop, or a hard-real-time scheduler. There you reach for a deamortized structure (see Variants) that converts the amortized bound into a true worst-case bound at a constant-factor cost.

Amortized vs the other complexity notions

	Worst-case	Average-case	Amortized	Expected (randomized)
What it bounds	One operation, worst input	One operation, random input	Sequence of ops, worst input	One op, worst input + coin flips
Guarantee type	Deterministic, per-op	Probabilistic	Deterministic, per-sequence	Probabilistic over randomness
Can an adversary break it?	No	Yes (bad input)	No (holds for any sequence)	No (randomness is internal)
Dynamic array push	O(n)	O(1)	O(1)	—
Hash table lookup	O(n)	O(1)	O(1) amortized w/ resize	O(1) expected (universal hashing)
Canonical example	Linked-list search	Quicksort on random data	Table doubling, union-find	Quicksort w/ random pivot, treap

The two most-confused rows are average-case and amortized. Average-case averages over a probability distribution of inputs and can be wrong on an unlucky input. Amortized averages over a sequence of operations on the worst-case input and is never wrong — any sequence of n pushes is guaranteed O(n) total, no probability involved. Expected (randomized) complexity is a third thing again: the average is taken over the algorithm's own internal coin flips, so even an adversarial input can't reliably defeat it.

What the numbers actually say

• 1,000,000 pushes ⇒ 20 resizes, < 2,000,000 copies. Doubling from capacity 1, resizes fire at 1, 2, 4, …, 524288 — that's 20 events copying 1,048,575 elements total, less than 2n.
• Growth factor changes the constant, not the class. Doubling wastes up to 50% of allocated memory; growing by 1.5× wastes at most 33% but does ~2× as many resizes. Both are O(1) amortized. Python's CPython list grows by roughly 1.125× (newsize + (newsize >> 3) plus a small constant); Go's runtime grows slices ~2× under 1024 elements then ~1.25×; Java's ArrayList grows 1.5×.
• Fixed-chunk growth is quadratic. Grow by a constant k and the i-th resize copies ~i·k elements; over n/k resizes that's Θ(n²/k) total — O(n) amortized per push, catastrophically worse than O(1).
• Why 1.5× and not 2×. A growth factor below the golden ratio (≈1.618) lets freed blocks be reused for the next allocation, reducing heap fragmentation. Facebook's folly fbvector documents picking 1.5× for exactly this reason.

JavaScript implementation

A dynamic array that counts the real cost of every push, so you can watch the amortized average converge to a constant:

class DynamicArray {
  constructor() {
    this.buf = new Array(1);   // backing store
    this.size = 0;             // logical length
    this.cap = 1;              // physical capacity
    this.totalCost = 0;        // running tally of real work
  }

  push(value) {
    if (this.size === this.cap) this._grow();   // expensive, but rare
    this.buf[this.size] = value;
    this.size++;
    this.totalCost += 1;                        // the cheap write
  }

  _grow() {
    const newCap = this.cap * 2;                // GEOMETRIC growth
    const bigger = new Array(newCap);
    for (let i = 0; i < this.size; i++) {       // copy is O(n)
      bigger[i] = this.buf[i];
      this.totalCost += 1;                      // count every copy
    }
    this.buf = bigger;
    this.cap = newCap;
  }

  get amortizedPerPush() {
    return this.size ? this.totalCost / this.size : 0;
  }
}

const a = new DynamicArray();
for (let i = 0; i < 1_000_000; i++) a.push(i);
console.log(a.amortizedPerPush.toFixed(3));  // ~2.049 — a flat constant

Run it for any n and the printed average hugs a constant near 2. That constant is the whole point: it never grows with n. Swap this.cap * 2 for this.cap + 4 (fixed-chunk growth) and watch the same average climb without bound — the amortized cost has silently become O(n).

Python: the potential method in code

This version reports the amortized cost using the potential function Φ = 2·size − capacity, and asserts after each push that Φ stays non-negative — the formal condition (Φ never drops below its initial value) that makes the bound valid.

class DynamicArray:
    def __init__(self):
        self.buf = [None]
        self.size = 0
        self.cap = 1

    def _phi(self):
        # Potential: stored "energy" that pays for the next resize.
        return 2 * self.size - self.cap

    def push(self, value):
        phi_before = self._phi()
        actual = 1                       # the write itself

        if self.size == self.cap:        # full -> resize
            new_cap = self.cap * 2
            bigger = [None] * new_cap
            for i in range(self.size):
                bigger[i] = self.buf[i]
            actual += self.size          # the O(n) copy
            self.buf, self.cap = bigger, new_cap

        self.buf[self.size] = value
        self.size += 1

        phi_after = self._phi()
        amortized = actual + (phi_after - phi_before)
        assert phi_after >= 0, "potential went negative — bound broken"
        return amortized                 # always 3, cheap or expensive push

arr = DynamicArray()
costs = [arr.push(i) for i in range(16)]
print(costs)   # [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Every entry in costs is 3, including the four pushes that triggered an O(n) resize. That uniformity is exactly what the potential method buys: the spikes in actual cost are smoothed into a flat amortized cost by the rising and falling potential.

Variants and famous applications

Deamortization. To turn amortized O(1) into worst-case O(1), keep two backing arrays during a grow phase. On each push, copy a constant number of old elements into the new array — enough to finish the migration before the new array itself fills. No single push ever copies more than a constant. This is how real-time-safe dynamic arrays work; the cost is roughly 2× memory during migration.

Hash-table rehashing. The exact same doubling argument makes hash-table insert O(1) amortized: when the load factor exceeds a threshold, allocate a table twice as big and rehash every key in O(n). Rare and geometric, so amortized O(1) per insert.

Union-Find with path compression + union by rank. Tarjan proved a sequence of m operations on n elements runs in O(m·α(n)), where α is the inverse Ackermann function — effectively a constant (≤ 4 for any n that fits in the universe). This is the deepest classical amortized result, and the potential method is the standard proof tool.

Splay trees. Each access rotates the touched node to the root. Any single access can be O(n), but a sequence of m accesses is O(m log n) amortized — proven with a logarithmic potential function. Hot keys drift toward the root and stay cheap.

Fibonacci heaps. decrease-key is O(1) amortized and extract-min is O(log n) amortized, achieved by lazily deferring cleanup work and paying for it later — the canonical "do the cheap thing now, pay at the next expensive op" structure. This is what gives Dijkstra its O(E + V log V) bound.

The binary counter. Incrementing a binary counter flips trailing 1s to 0 and one 0 to 1. A single increment can flip all k bits (O(k)), but n increments flip fewer than 2n bits total — bit i flips only every 2ⁱ increments. Amortized O(1) per increment, the textbook warm-up before table doubling.

Common pitfalls and edge cases

• Growing by a constant. The single most common mistake. cap += 16 looks innocuous and turns push into O(n) amortized. Growth must be multiplicative.
• Grow/shrink thrashing. If you shrink the array when it's half empty and grow when it's full, an adversary alternating push/pop at the boundary forces an O(n) resize on every operation — amortized O(n). Fix: shrink only at quarter-full (so grow at full and shrink at ¼ leave a buffer), which restores amortized O(1).
• Confusing amortized with average-case. Amortized is a deterministic worst-case-sequence guarantee; average-case is probabilistic. Saying "push is O(1) on average" is a weaker, different claim.
• Assuming amortized means low latency. A single push can still stall for O(n). Don't put an amortized structure on a hard-real-time path without deamortizing it first.
• Letting the potential go negative. In a proof, Φ ≥ 0 at all times is what makes the sum of amortized costs upper-bound the real cost. A potential function that dips below its starting value invalidates the bound — a subtle proof bug, not a code bug.
• Forgetting the cheap-op count. Amortized analysis bounds the total — the n cheap writes plus the < 2n copies. Counting only the resizes undersells the real work (though it stays O(n)).