Introduction to Amortized Analysis

Here's a puzzle: Dynamic arrays (like ArrayList in Java or list in Python) claim O(1) append time. But occasionally, when the array is full, they must:

1. Allocate a new array (typically 2x the size)
2. Copy all existing elements to the new array
3. Insert the new element

Copying n elements is O(n)—clearly not O(1). So how can we claim O(1) append?

The answer is amortized analysis—a technique that analyzes the average cost per operation over a sequence of operations, rather than the worst case of a single operation.

The key insight:

That expensive O(n) copy happens so infrequently that when we spread its cost across all the cheap O(1) appends that preceded it, the average cost per operation is still O(1).

The core idea:

Amortized analysis computes the average cost per operation over a worst-case sequence of operations.

Notice the nuance:

• Average case: Average over random/typical inputs
• Worst case: Cost of a single worst-case operation
• Amortized: Average per-operation cost over the worst possible sequence of operations

Why is this different from average case?

Average-case analysis assumes a probability distribution over inputs. Amortized analysis makes no distributional assumptions—it guarantees that any sequence of n operations takes at most f(n) total time, so the average is at most f(n)/n per operation.

Intuitive analogy: Paying off debt

Imagine expensive operations as "going into debt." Cheap operations "pay down the debt." If expensive operations are rare enough, the cheap operations can cover the debt, keeping the average cost low.

Formal definition (simplified):

For a data structure with operations:

The amortized cost of an operation is the average cost per operation in the worst-case sequence of n operations, as n approaches infinity.

If we can show that any sequence of n operations takes O(n) total time, then the amortized cost per operation is O(1).

What amortized analysis IS:

• A guarantee about total cost over sequences
• A bound that holds for ALL sequences, not just random ones
• A way to understand data structures where occasional expensive operations enable many cheap ones

What amortized analysis is NOT:

• A probabilistic statement (no assumptions about input distribution)
• A guarantee about any single operation (individual ops can be expensive)
• Average-case analysis (no probability needed)

The dynamic array's append operation is the canonical example of amortized analysis. Let's work through it carefully.

How dynamic arrays grow:

A dynamic array maintains:

• An underlying fixed-size array
• A count of how many elements are used
• When full, allocate a new array (typically 2x size) and copy elements

Cost breakdown:

Let's trace appending n elements to an initially empty array with capacity 1:

Counting total cost for n appends:

Resizing happens at capacities 1, 2, 4, 8, 16, ... up to n.

• Resize at capacity 1: copy 1 element
• Resize at capacity 2: copy 2 elements
• Resize at capacity 4: copy 4 elements
• ...
• Resize at capacity n/2: copy n/2 elements (last resize before n)

Total copy cost: 1 + 2 + 4 + 8 + ... + n/2 = n - 1 (geometric series sums to ~n)

Total insert cost: n (one insert per append)

Total cost for n appends: ~2n = O(n)

Amortized cost per append: O(n) / n = O(1)

Despite occasional O(n) resizes, the amortized cost per operation is constant!

The accounting intuition:

Think of it this way: each element "pays" for its future copy.

• When we insert element i at cost 1, charge it 2 (overpay by 1).
• The extra 1 goes into a "bank."
• When resize happens, the bank has enough to pay for copying.

Every element pays 2 (constant), and resizes are "free" because we've pre-paid.

This "banker's method" is one formal approach to proving amortized bounds. The intuition: cheap operations save up credit; expensive operations spend it.

Amortized analysis is applicable when:

1. Expensive operations are rare and enable cheap operations

The pattern is: do something expensive occasionally that makes subsequent operations cheap.

• Dynamic array: Expensive resize enables many cheap inserts
• Hash table rehash: Expensive rehash reduces future collision chains
• Splay tree access: Expensive rotation brings frequently-accessed nodes near root

2. Expensive operations have diminishing frequency

The key is that expensive operations can't happen too often:

• Dynamic array doubles: Resize happens at 1, 2, 4, 8, 16... (exponentially decreasing frequency)
• Not: Resize happens every 10 operations (would kill amortized bound)

3. We care about total work, not individual operation latency

Amortized analysis doesn't bound individual operations—some may be slow. Use when:

• Processing a batch of operations
• Total throughput matters more than per-operation latency
• Occasional slowdowns are acceptable

When amortized analysis does NOT apply:

Real-time systems:

Amortized O(1) means some operations might take O(n). For real-time systems that must respond within a deadline, amortized bounds are insufficient.

Example: An embedded controller using a dynamic array might miss a deadline during resize. Real-time systems need worst-case O(1) approaches (like pre-allocated fixed arrays or incremental resizing).

Latency-sensitive operations:

If each operation needs consistent latency (not just good average), amortized is misleading:

• User-facing request handling
• Interactive UI updates
• High-frequency trading

Adversarial scenarios:

If an adversary can trigger expensive operations repeatedly by timing their requests to coincide with expensive phases, amortized bounds don't help.

Let's explore more examples to cement the amortized analysis intuition.

Example 1: Binary Counter Increment

Consider a k-bit binary counter incrementing from 0 to 2ᵏ - 1:

000 → 001 → 010 → 011 → 100 → 101 → 110 → 111

Naive analysis (worst case): Incrementing can flip up to k bits (e.g., 0111 → 1000). k = O(log n) for n increments. Worst case per increment: O(log n).

Amortized analysis:

• Bit 0 flips every increment: n times total
• Bit 1 flips every 2 increments: n/2 times total
• Bit 2 flips every 4 increments: n/4 times total
• Bit k flips every 2ᵏ increments: n/2ᵏ times total

Total flips: n + n/2 + n/4 + ... + 1 ≤ 2n = O(n)

Amortized cost per increment: O(n) / n = O(1)

Despite worst case O(log n), amortized is O(1)!

Example 2: Multi-Pop Stack

Consider a stack with three operations:

• Push(x): push one element — O(1)
• Pop(): pop one element — O(1)
• MultiPop(k): pop k elements (or until empty) — O(min(k, n))

Naive analysis: MultiPop can be O(n). Sequence of operations could be "push n, multipop n" costing O(n) for multipop.

Amortized analysis:

Key insight: each element can only be popped once!

Starting from empty, after any sequence of operations:

• Total pushes = P
• Total individual pops ≤ P (can't pop what wasn't pushed)
• Total multipop element removals ≤ P

Total work from all pops ≤ P = O(n) for n operations.

Amortized cost per operation: O(1)

Even MultiPop is O(1) amortized because you can't pop more than you pushed.

Example 3: Hash Table with Rehashing

Hash tables rehash when load factor exceeds threshold (typically 0.7 or 0.75):

• Insert: O(1) expected, unless rehash needed
• Rehash: O(n) — create new table, reinsert all elements

Amortized analysis (similar to dynamic array):

With doubling capacity:

• Rehash at n=1, 2, 4, 8, 16...
• Total rehash work for n inserts: 1 + 2 + 4 + ... + n/2 = O(n)
• Insert work: O(n)

Amortized cost per insert: O(1)

Note: This is amortized on top of the expected O(1) for hash table operations. Hash tables have:

• Expected O(1) per operation (averaging over hash function behavior)
• Amortized O(1) for resize (averaging over operation sequence)

Both analyses are needed for the complete picture.

Let's precisely distinguish these three analytical frameworks with a side-by-side comparison.

Visual intuition:

Imagine a graph of operation costs over a sequence:

Cost
  |
  |     *         (Worst case bounds every point)
  |     |
  |---*-|------*--------- Worst case bound
  |  *  |     *
  |* *  *   * *
  |**  * * * * *
  +-----------------------> Operations
       ↑
       Expensive op

• Worst case: Bounds the highest spike
• Average case: Averages heights assuming random distribution
• Amortized: Averages heights over the sequence

For the graph above:

• Worst case: high (the spike)
• Average case: depends on distribution assumptions
• Amortized: total area ÷ number of operations (low if spikes are rare)

Understanding amortized analysis changes how you reason about code and data structure choices.

Implication 1: ArrayList vs. LinkedList

The classic debate: Which is better for appending elements?

Despite LinkedList having "true" O(1) append (no resizing ever), ArrayList often wins because:

• Amortized O(1) is nearly as good in practice
• Better cache locality (contiguous memory)
• Lower memory overhead

The lesson: Amortized O(1) is usually acceptable; don't choose worse data structures just to avoid occasional expensive operations.

Implication 2: Understanding "Occasional Spikes"

Profiling code might show occasional slow operations. Before panicking:

• Is this a resize/rehash spike? (Expected, amortized away)
• Is this garbage collection? (Often related to allocation during resize)
• Does it affect overall throughput? (If amortized cost is acceptable, OK)

Knowing amortized analysis helps you triage: some spikes are designed; others are bugs.

Implication 3: Pre-sizing to avoid spikes

If you know the final size, pre-allocate:

# Python: pre-size list
data = [None] * expected_size

# Java: pre-size ArrayList
List<Integer> data = new ArrayList<>(expectedSize);

# Java: pre-size HashMap
Map<K, V> map = new HashMap<>(expectedSize);

This eliminates resize spikes entirely, turning amortized O(1) into true O(1).

Implication 4: Incremental resizing

For systems that can't tolerate spikes, use incremental approaches:

• Incremental rehashing: Spread rehash work across multiple operations
• Two-table hash: Migrate entries gradually from old to new table
• Ring buffers: Fixed size, no resize needed

These trade implementation complexity for bounded worst-case time.

Amortized analysis provides a powerful middle ground between overly pessimistic worst-case bounds and probability-dependent average-case bounds.

What's next:

We've established the conceptual foundation. The next page brings amortized analysis to life with real-world examples—systems where amortized thinking explains observed performance and guides engineering decisions.