Amortized Analysis: When O(1) Is Really O(1)

When someone says a data structure is "O(1) amortized," they're making a precise mathematical claim that individual operations can be expensive as long as a sequence of operations is cheap on average. This article dissects the three canonical methods for proving amortized bounds and shows why naive worst-case analysis misses the real story.

Why Worst-Case Analysis Fails

Consider a dynamic array (like std::vector or ArrayList). Most appends are O(1) — you just write to the next slot. But occasionally you trigger a resize: allocate a new buffer, copy every element, free the old one. That single operation is O(n).

Worst-case analysis says every append is O(n). That's technically correct but practically useless. Amortized analysis gives us the tighter bound we need.

// Dynamic array append — the resize is O(n)
void vector_push_back(Vector *v, int val) {
    if (v->size == v->capacity) {
        v->capacity *= 2;
        v->data = realloc(v->data, v->capacity * sizeof(int));
    }
    v->data[v->size++] = val;
}

Aggregate Method

The simplest approach: sum the total cost of n operations and divide by n.

For dynamic array resizing, let's count the total cost of n sequential appends:

n operations total
Resizes happen at sizes 1, 2, 4, 8, ..., 2^k where 2^k ≤ n
Cost of each resize: 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 2n
Total cost: n (writes) + 2n (copies) = 3n
Amortized cost per operation: 3n / n = O(1)

def amortized_cost_of_n_appends(n: int) -> int:
    total_copy_cost = 0
    capacity = 1
    for i in range(n):
        if i == capacity:
            total_copy_cost += capacity
            capacity *= 2
    return n + total_copy_cost  # n writes + copies
 
# n = 1_000_000
# total_copy_cost ≈ 1,048,576 (close to n)
# amortized per operation ≈ 2.0 — O(1)

Accounting Method

Assign each operation a "charge" — the amortized cost. Some operations overcharge (build credit), others undercharge (spend credit). The credit pool must never go negative.

// Each cheap append is charged 3 units:
//   1 for the write itself
//   1 saved as credit toward a future resize
//   1 saved to pay for copying this element during a resize
//
// When resize triggers:
//   We have n credits saved (1 per element in the array)
//   The resize costs n copies + 1 write = n + 1
//   The n credits cover it exactly

The accounting method is intuitive but requires careful assignment of charges. The potential method formalizes it.

Potential Method

Define a potential function Φ that maps data structure state to a non-negative value. The amortized cost is:

â_i = c_i + Φ(D_i) - Φ(D_{i-1})

Where c_i is the actual cost and Φ(D_i) is the potential after operation i.

class DynamicArray:
    def __init__(self):
        self.data = []
        self.capacity = 1
 
    def potential(self) -> int:
        """Φ = 2 * size - capacity
        Positive when underutilized (credit), negative when tight (debt).
        Never goes below zero because resize doubles capacity."""
        return 2 * len(self.data) - self.capacity
 
    def amortized_cost(self, element) -> int:
        actual_cost = 1  # the write
        old_potential = self.potential()
        self._maybe_resize()
        self.data.append(element)
        new_potential = self.potential()
        return actual_cost + new_potential - old_potential
 
    def _maybe_resize(self):
        if len(self.data) == self.capacity:
            self.capacity *= 2
            # actual cost is len(self.data) for copying

Real-World Example: Stack with Multipop

Consider a stack supporting push, pop, and multipop(k) which pops min(k, size) elements:

void multipop(Stack *s, int k) {
    int count = 0;
    while (!stack_empty(s) && count < k) {
        stack_pop(s);
        count++;
    }
}

Worst case for multipop is O(n). But over a sequence of n operations (pushes, pops, and multipops), the total number of pops cannot exceed the total number of pushes. Aggregate analysis: n pushes + m pops ≤ 2n total element operations → O(1) amortized.

Real-World Example: Splay Trees

Splay trees are the canonical example where amortized analysis gives a bound that worst-case cannot match. Every access is O(log n) amortized, but no single access is guaranteed O(log n) — some individual accesses are O(n).

// Splay tree: rotate the accessed node to the root
// Single access: O(n) worst case
// Sequence of m accesses: O(m log n) amortized
// No comparison-based structure can do better for arbitrary access patterns

Synthesis

Amortized analysis bridges the gap between theoretical worst-case bounds and practical performance. The aggregate method is simplest, the accounting method is most intuitive, and the potential method is most general. Master all three — they appear throughout systems design, from hash table resizing to garbage collector analysis to network congestion control.