Amortized Analysis: The True Cost of Operations

Terminology

What & Why

Worst-case analysis can be misleading. A dynamic array's push operation is $O(n)$ in the worst case (when it needs to resize), but most pushes are $O(1)$. If you analyze a sequence of $n$ pushes using worst-case per-operation analysis, you get $O(n^2)$. But the actual total cost is $O(n)$, giving an amortized cost of $O(1)$ per push.

Amortized analysis gives you the true cost of a sequence of operations. It does not use probability or averages over random inputs. It guarantees that for any sequence of $n$ operations, the total cost is bounded, and the per-operation average of that bound is the amortized cost.

This matters whenever you use data structures with occasional expensive operations: dynamic arrays, hash tables with rehashing, splay trees, Fibonacci heaps, or union-find with path compression. The amortized cost tells you the real performance story.

How It Works

Method 1: Aggregate Method

Count the total cost of $n$ operations, then divide by $n$.

Dynamic array example: Start with capacity 1. When full, double the capacity and copy all elements.

For $n$ pushes, resizing happens at pushes 1, 2, 4, 8, 16, ..., costing 1 + 2 + 4 + 8 + ... + $n$ copies. This geometric series sums to at most $2n$. Adding the $n$ individual push costs: total $\le 3n$. Amortized cost: $3n / n = O(1)$.

Method 2: Accounting Method

Assign each operation an amortized cost. Cheap operations pay more than their actual cost, banking credit. Expensive operations use that credit.

Dynamic array: Charge each push an amortized cost of 3 units:

• 1 unit for the push itself
• 2 units saved as credit (1 for copying this element later, 1 for copying a matching old element)

When a resize happens at capacity $k$, we need to copy $k$ elements. But we have $k/2$ elements that each saved 2 credits (they were inserted since the last resize), giving $k$ credits total. The resize is fully paid for.

Method 3: Potential Method

Define a potential function $\Phi(D_i)$ on the state of the data structure after operation $i$. The amortized cost of operation $i$ is:

The total amortized cost telescopes:

If $\Phi(D_n) \ge \Phi(D_0)$ (typically both start at 0), then the total amortized cost is an upper bound on the total actual cost.

Dynamic array potential: Let $\Phi = 2 \cdot \text{size} - \text{capacity}$.

• After a push without resize: $\Phi$ increases by 2 (size goes up by 1). Amortized cost: $1 + 2 = 3$.
• After a push with resize from capacity $k$ to $2k$: actual cost is $k + 1$ (copy $k$ elements + 1 push). $\Phi$ changes from $2k - k = k$ to $2(k+1) - 2k = 2$. Change in $\Phi$: $2 - k$. Amortized cost: $(k+1) + (2 - k) = 3$.

Both cases give amortized cost 3. Consistent with the other methods.

Complexity Analysis

Implementation

ALGORITHM DynamicArrayPush(array, element)
INPUT: array: dynamic array with size and capacity, element: value to add
OUTPUT: updated array
BEGIN
  IF array.size = array.capacity THEN
    newCapacity <- array.capacity * 2
    newData <- ALLOCATE array of size newCapacity
    FOR i <- 0 TO array.size - 1 DO
      newData[i] <- array.data[i]
    END FOR
    array.data <- newData
    array.capacity <- newCapacity
  END IF

  array.data[array.size] <- element
  array.size <- array.size + 1
END

ALGORITHM AmortizedCostAggregate(operations, n)
INPUT: operations: sequence of n operations, n: count
OUTPUT: amortized cost per operation
BEGIN
  totalCost <- 0
  FOR i <- 1 TO n DO
    totalCost <- totalCost + ActualCost(operations[i])
  END FOR
  RETURN totalCost / n
END

ALGORITHM PotentialMethodCost(actualCost, phiBefore, phiAfter)
INPUT: actualCost: real cost of operation, phiBefore: potential before, phiAfter: potential after
OUTPUT: amortized cost of this operation
BEGIN
  RETURN actualCost + (phiAfter - phiBefore)
END

ALGORITHM MultiPopStack_Amortized(stack, k)
INPUT: stack: stack with n elements, k: number to pop
OUTPUT: popped elements
BEGIN
  popped <- empty list
  count <- MIN(k, stack.size)
  FOR i <- 1 TO count DO
    popped <- popped + [POP(stack)]
  END FOR
  RETURN popped
END

Real-World Applications

• Dynamic arrays everywhere: JavaScript arrays, Python lists, Java ArrayLists, and C++ vectors all use doubling strategies with $O(1)$ amortized push, justified by amortized analysis
• Hash table rehashing: when a hash table's load factor exceeds a threshold, it rehashes all entries into a larger table; amortized analysis proves this keeps insert at $O(1)$ average
• Splay trees in caching: splay trees provide $O(\log n)$ amortized access and naturally move frequently accessed items to the root, making them effective for cache implementations
• Garbage collection: generational garbage collectors amortize the cost of collection over many allocations; most collections are cheap (young generation), with rare expensive full collections
• Network buffer management: network stacks use amortized analysis to justify buffer allocation strategies where occasional large allocations are spread across many small packet arrivals

Key Takeaways

• Amortized analysis gives the true average cost per operation over a worst-case sequence, not a probabilistic average
• Three methods (aggregate, accounting, potential) always give the same answer; choose whichever is most natural for the problem
• The potential method is the most general: define $\Phi$ so that cheap operations increase potential and expensive operations decrease it
• Dynamic array push is the canonical example: $O(n)$ worst case but $O(1)$ amortized, because resizes are exponentially rare
• Amortized analysis is essential for understanding the real performance of hash tables, splay trees, Fibonacci heaps, and union-find