Amortized Analysis

By the end you will be able to bound the total cost of a whole sequence of operations — even when a few individual operations are expensive — using the three standard techniques: aggregate analysis, the accounting method, and the potential method. You will apply all three to a stack with MULTIPOP, a binary counter with INCREMENT, and a dynamic table that grows and shrinks itself, and see exactly why a careless resizing rule can quietly turn an O(1) operation into an O(n) one.

1. What "amortized" means (and what it does not mean)

This is easy to confuse with two other ideas, so let's separate them clearly:

• Worst-case analysis (as in the sorting, graph and greedy lessons) bounds the cost of one operation, in the worst input for that one operation.
• Average-case analysis (probabilistic analysis) assumes a probability distribution over inputs and bounds the expected cost.
• Amortized analysis (this lesson) makes no assumption about probability at all. It is a worst-case guarantee for a sequence of operations — it simply guarantees the sequence's total cost is small, even though individual operations inside it can occasionally be expensive. There is no "unlucky" input that can break an amortized bound, unlike an average-case bound.

There are three standard techniques for proving an amortized bound, all producing valid (though sometimes different-looking) bounds on the same sequence of operations:

• Aggregate analysis: bound the total cost T(n) of n operations directly, then say every operation "costs" T(n)/n on average — the same amortized cost is assigned to every operation type.
• The accounting method: assign each operation type its own fixed "amortized price" ĉ, overcharging some ops to build up credit that pays for other, undercharged ops later.
• The potential method: define a single number Φ (the "potential") that summarizes the whole data structure's stored-up capacity to absorb future work, and derive each operation's amortized cost from how Φ changes.

We will apply all three to two running examples — a stack with MULTIPOP, and a binary counter with INCREMENT — before moving to dynamic tables.

2. Aggregate analysis: MULTIPOP on a stack

The multipop operation in pseudocode (push and pop are the O(1) primitives of any stack):

A single multipop(k) call costs min(size of S, k) — in the worst case, that's Θ(n) if the stack holds n items. Doing this n times naively suggests Θ(n²) total. But aggregate analysis looks at the whole sequence at once: every object popped (whether by POP or by a POP inside MULTIPOP) must have been pushed at some point, and each object can only be popped once. So across any sequence of n PUSH/POP/MULTIPOP operations, the total number of POPs performed can never exceed the total number of PUSHes, which is at most n. Total actual cost ≤ n (pushes) + n (pops) = 2n, so the amortized cost per operation is O(1), even though some individual MULTIPOP calls cost Θ(n).

The aggregate argument as running code: the worst single call and the whole-sequence total side by side.

class Stack17 {
  final List<int> _s = [];
  int get size => _s.length;
  int push(int x) { _s.add(x); return 1; }
  int pop() {
    if (_s.isEmpty) return 0;
    _s.removeLast();
    return 1;
  }
  int multipop(int k) {
    var popped = 0;
    while (_s.isNotEmpty && popped < k) {
      _s.removeLast();
      popped++;
    }
    return popped;
  }
}

Input size → what’s feasible: n = 10⁶ mixed PUSH/POP/MULTIPOP operations → at most 2n = 2·10⁶ elementary steps in total (milliseconds), even though the “each MULTIPOP could cost n” view suggests n² = 10¹².

3. Aggregate analysis: INCREMENT on a binary counter

A k-bit counter is an array bits[0..k−1] of bits, where bits[0] is least significant. Its value is Σ bits[i]·2ⁱ. Here is the increment operation (0-indexed, bits[0] is the least significant bit):

A single INCREMENT can flip all k bits (going from all-1s to all-0s, e.g. 111→000 with the carry conceptually overflowing past the array — the final guard "if i < bits.length" simply drops that overflow bit). So the naive worst-case bound for n INCREMENTs is Θ(nk). But look at how often each individual bit flips: bit bits[0] flips on every single INCREMENT (n times); bits[1] flips every 2nd INCREMENT (⌊n/2⌋ times); bits[i] flips every 2ⁱ-th INCREMENT (⌊n/2ⁱ⌋ times). Summing a geometric series:

total flips = Σ_i=0^k−1 ⌊n/2ⁱ⌋ < n·Σ_i=0^∞ 1/2ⁱ = 2n

So n INCREMENTs cost less than 2n bit-flips total — amortized O(1) per INCREMENT, even though individual calls can cost up to k.

The geometric-series bound as code: count how often each bit flips and compare with floor(n / 2i) and with 2n:

class Counter17 {
  final List<int> bits;
  Counter17(int k, [int start = 0]) : bits = List.filled(k, 0) {
    var x = start;
    for (var i = 0; i < k && x > 0; i++) {
      bits[i] = x & 1;
      x >>= 1;
    }
  }
  int increment() {
    var i = 0, cost = 0;
    while (i < bits.length && bits[i] == 1) {
      bits[i] = 0;
      i++;
      cost++;
    }
    if (i < bits.length) {
      bits[i] = 1;
      cost++;
    }
    return cost;
  }
}

Input size → what’s feasible: k = 64-bit counter, n = 10⁹ INCREMENTs → fewer than 2·10⁹ bit writes in total (about 2 per call), not k·n = 6.4·10¹⁰.

4. The accounting method: MULTIPOP

This works as long as the bank balance (total credit) never goes negative — and it can't, here, because the credit taped to a plate is always still there (equal to $1) until that exact plate is popped, so the bank balance always exactly equals the current number of plates on the stack (≥ 0, always).

The accounting invariant as code (credit is the bank balance, charged the made-up price):

var credit = 0;
// after each op: charged - actual is added to credit
// PUSH: charged=2; POP/MULTIPOP: charged=0
credit += charged - actual;
// invariant, must ALWAYS hold:
// credit == s.size  &&  credit >= 0

5. The accounting method: INCREMENT

One INCREMENT resets some number of bits (each paid for free, from their own credit) and then sets at most one new bit to 1 (charged $2). So the amortized cost of any single INCREMENT, under this pricing, is at most 2 — regardless of how many bits it resets. The bank balance always equals the number of 1-bits currently in the counter, which is never negative.

The same idea for the counter, run for 40 INCREMENTs of a 5-bit counter (so it includes an overflow):

6. The potential method: MULTIPOP & the correctness argument

The recipe: pick Φ so that Φ(D₀) = 0 (start) and Φ(Dᵢ) ≥ 0 always. Then define each operation's amortized cost as:

ĉᵢ = cᵢ + Φ(Dᵢ) − Φ(D_i−1)

Summing over all n operations, the Φ terms telescope (each Φ(Dᵢ) cancels the next term's −Φ(Dᵢ)):

Σᵢ ĉᵢ = Σᵢ cᵢ + Φ(D_n) − Φ(D₀)

Since Φ(D₀) = 0 and Φ(D_n) ≥ 0, this proves Σ cᵢ ≤ Σ ĉᵢ — the real total cost is bounded by the sum of amortized costs. This telescoping identity is itself the whole correctness proof — there is no separate "loop invariant" needed the way a sorting algorithm needs one; proving Φ(D₀)=0 and Φ(Dᵢ)≥0 for all i, plus computing ĉᵢ = cᵢ+ΔΦ for each operation type, is the proof.

For the stack, Φ(D) = (number of objects currently on the stack). PUSH: ΔΦ=+1, so ĉ = 1+1 = 2. POP: ĉ = 0. MULTIPOP(k) popping k′ = min(k, size) objects: ΔΦ = −k′, so ĉ = k′ − k′ = 0. Every operation's amortized cost is O(1), matching the accounting method's numbers exactly (that's not a coincidence — Φ = credit balance here).

The potential method for the stack as code, with the telescoping identity checked exactly:

Try your own sequence of stack operations (comma-separated, e.g. PUSH 4, PUSH 7, MULTIPOP 2, POP, MULTIPOP 10):

check(totalAmortized, totalActual + phiPrev - 0,
    'telescoping identity: sum(amortized) == sum(actual) + Phi_n - Phi_0 (trial $trial)');

7. The potential method: INCREMENT (and why DECREMENT breaks it)

Let Φ(D) = bᵢ = number of 1-bits after operation i. If INCREMENT resets tᵢ bits, its actual cost is ≤ tᵢ+1 (the resets, plus at most one set). Whatever happens, bᵢ ≥ b_i−1 − tᵢ + 1 (you lose the tᵢ bits you reset but gain at least the one you might set), so ΔΦ ≥ 1 − tᵢ, giving:

ĉᵢ = cᵢ + ΔΦ ≤ (tᵢ+1) + (1−tᵢ) = 2

Every INCREMENT's amortized cost is at most 2, regardless of how many bits it resets — matching the aggregate 2n bound and the accounting numbers, as it must.

A bonus the potential method makes easy: this argument works even if the counter does not start at 0. If it starts with b₀ ones, then total actual cost = Σĉᵢ − Φ(D_n) + Φ(D₀) ≤ 2n − b_n + b₀ (every ĉᵢ ≤ 2, and the bound is tight unless an overflowing call, which amortizes to 0, occurs) — still O(n) as long as n = Ω(k) (since b₀ ≤ k always). Try it (format k=6, start=45, n=20 — k = number of bits, start = initial value, n = number of INCREMENTs):

The same page example (k=6, start=45, n=20) as code, with that bound checked:

8. Dynamic tables: insert (expansion only)

A table tracks num (items currently stored) and size (slots allocated). The load factor α = num / size measures how full it is (an empty table has α defined as 1). The insert operation doubles the table whenever it's exactly full:

Doubling keeps α(T) ≥ 1/2 always (right after doubling, before the new item goes in, the table is exactly half full; it only gets fuller from there until the next doubling). Aggregate analysis: inserting item i costs i if i−1 was an exact power of two (an expansion, copying i−1 old items plus inserting the new one), else it costs 1. Summing a geometric series of doublings gives total cost < n + 2n = 3n for n inserts — amortized ≤ 3 per insert.

The aggregate total and the potential Φ = 2·num − size as code for n = 1,000 inserts:

Normal case — 10 inserts from an empty table, watch it double at sizes 1, 2, 4, 8:

Edge & worst case — zooming into inserts #6 through #10, right around the moment insert #9 triggers an expansion (the most expensive single insert in this run, since 9−1=8 is a power of two):

Try your own number of inserts (1 to 40) and watch the potential Φ = 2·num − size rise and crash in a sawtooth pattern:

class DynamicTable17 {
  List<int?> table = [];
  int size = 0;
  int num = 0;
  int insert(int x) {
    var cost = 0;
    if (size == 0) {
      table = List<int?>.filled(1, null);
      size = 1;
    }
    if (num == size) {
      final newTable = List<int?>.filled(2 * size, null);
      for (var i = 0; i < size; i++) {
        newTable[i] = table[i];
        cost++;
      }
      table = newTable;
      size = 2 * size;
    }
    table[num] = x;
    cost++;
    num++;
    return cost;
  }
}

Input size → what’s feasible: n = 10⁶ inserts → total cost < 3·10⁶ (about 2 per insert) and the table never holds more than 2n slots; growing by +1 instead of doubling would cost n²/2 = 5·10¹¹ copies.

9. Dynamic tables: delete (expansion + contraction)

Here is delete in pseudocode (remove the last item, then shrink to half size if that leaves the table below a chosen load-factor threshold):

Normal case — a mixed sequence of inserts and deletes, using the fixed rule (contract only when the load factor would drop below 1/4, not 1/2). Watch num, size and Φ (defined below) move together, staying O(1) amortized per operation:

The potential Φ (defined below) on a mixed run of inserts and deletes (the 1/4 rule): every amortized cost stays a small constant and Φ never goes negative:

Worst case — this is the important one. Fill a table completely (num = size = S), then alternate INSERT, DELETE forever. Compare the naive rule (grow at full, shrink whenever load ≤ 1/2 — the same threshold value used for both directions, with no buffer between them) against the fixed rule (grow at full, shrink only below 1/4):

The two rules as a tiny cost model (ResizeModel only counts copies; the rule is just two functions), run on the full-table adversary from above:

Input size → what’s feasible: 10⁶ alternating INSERT/DELETE on a full table of 5·10⁵ slots → naive rule: ≈ 10⁶·5·10⁵ = 5·10¹¹ copies (never finishes); fixed 1/4 rule: ≈ 10⁶ + one 5·10⁵-item resize.

Try your own sequence of inserts/deletes on the fixed (1/4-threshold) table (comma-separated I/D, e.g. I,I,I,D,I,D,D,I,I,I,D,D,D,D):

class DynamicTable2 {
  // ... same insert() as DynamicTable17 above ...
  int delete(int idx) {
    var cost = 0;
    table[idx] = table[num - 1];
    table[num - 1] = null;
    num--;
    cost++;
    if (num == 0) {
      table = [];
      size = 0;
    } else if (num / size < 0.25) {
      final newSize = size ~/ 2;
      final newTable = List<int?>.filled(newSize, null);
      for (var i = 0; i < num; i++) {
        newTable[i] = table[i];
        cost++;
      }
      table = newTable;
      size = newSize;
    }
    return cost;
  }
}

Quiz

Interview questions

Cheat sheet

All three techniques prove valid bounds on the same real sequence of operations — they can (and often do) produce different-looking intermediate numbers (e.g. accounting's per-type ĉ vs potential's per-call ĉ), but the final asymptotic bound they certify is identical.