Amortized Analysis

Amortized analysis determines the average cost of operations in a worst-case sequence. Unlike average-case analysis (which averages over random inputs), amortized analysis guarantees cost bounds over ANY sequence of operations.

Three Methods

Aggregate Analysis

Count the total cost of n operations. Amortized cost per operation = total / n.

Example: Dynamic array (Vec) with n push operations.

Most pushes cost O(1). Resizing (doubling capacity) costs O(current_size). Resizes happen at sizes 1, 2, 4, 8, ..., 2^k.

Total cost = n (regular pushes) + (1 + 2 + 4 + ... + n) (resize copies)
           = n + 2n - 1
           = 3n - 1
           = O(n)

Amortized cost per push = O(n) / n = O(1)

Accounting Method

Assign an amortized cost (charge) to each operation. Some operations are overcharged (creating "credit"). Other operations use stored credit.

Invariant: Total credit must always be ≥ 0 (we never "go into debt").

Example: Dynamic array push.

Charge 3 units per push (actual cost of most pushes is 1).

Push (no resize): pay 1 unit, save 2 units as credit on the new element.
Push (resize): pay 1 unit for the push.
  Resizing: move n/2 elements → costs n/2 units.
  But: the n/2 elements added since the last resize each have 2 credits.
  Use their 2 × (n/2) = n credits → n credits ≥ n/2 cost.

Credit balance is always ≥ 0. Amortized cost per push: 3 = O(1). ✓

Potential Method

Define a potential function Φ mapping the data structure state to a non-negative real number. The amortized cost of operation i:

ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)

where cᵢ is the actual cost, Dᵢ is the state after operation i.

Total amortized cost = Σ ĉᵢ = Σ cᵢ + Φ(Dₙ) - Φ(D₀).

If Φ(Dₙ) ≥ Φ(D₀) (typically Φ(D₀) = 0 and Φ ≥ 0), then Σ ĉᵢ ≥ Σ cᵢ.

Example: Dynamic array. Φ = 2 × (size - capacity/2).

After resize: size = capacity/2 + 1, so Φ = 2.
Before next resize: size = capacity, so Φ = capacity.

Push (no resize): actual cost = 1.
  Φ increases by 2 (one more element, capacity unchanged).
  ĉ = 1 + 2 = 3.

Push (resize from capacity k to 2k): actual cost = 1 + k (copy k elements).
  Φ drops from 2(k - k/2) = k to 2(k/2 + 1 - k) = 2.
  Change: 2 - k.
  ĉ = (1 + k) + (2 - k) = 3.

Every operation has amortized cost 3 = O(1). ✓

Classic Examples

Multi-Pop Stack

A stack with operations: push(x) O(1), pop() O(1), multi_pop(k) pops k elements O(k).

Worst case for single operation: multi_pop(n) = O(n).

Amortized analysis: Each element is pushed at most once and popped at most once. In n operations, total pops ≤ total pushes ≤ n. So n operations cost O(n). Amortized: O(1) per operation.

Binary Counter

Incrementing an n-bit binary counter.

Worst case for single increment: O(n) bits flip (e.g., 0111...1 → 1000...0).

Amortized: Bit i flips every 2ⁱ increments. In n increments:

Total flips = n/1 + n/2 + n/4 + ... < 2n

Amortized cost per increment: O(1).

Potential method: Φ = number of 1-bits. Each increment: one 0→1 flip (+1 to Φ), some 1→0 flips (-k to Φ). ĉ = (k+1) + (1-k) = 2 = O(1).

Splay Tree

Splay operations have O(n) worst-case per operation, but O(log n) amortized.

Potential: Φ = Σ log(size(v)) for all nodes v (sum of log of subtree sizes).

The amortized analysis shows that each splay operation costs O(log n) amortized, using the potential function to account for the restructuring that improves future operations.

Fibonacci Heap

| Operation | Worst Case | Amortized | |---|---|---| | insert | O(1) | O(1) | | find-min | O(1) | O(1) | | merge | O(1) | O(1) | | extract-min | O(n) | O(log n) | | decrease-key | O(log n) | O(1) | | delete | O(n) | O(log n) |

Potential: Φ = trees + 2 × marked_nodes. Insert and merge just add trees (lazy). Extract-min consolidates trees (expensive but reduces Φ). Decrease-key uses cascading cuts (bounded by Φ).

Union-Find

With union by rank + path compression: O(α(n)) amortized per operation.

α(n) = inverse Ackermann function ≤ 4 for all practical n. Effectively O(1).

Amortized vs Average-Case vs Worst-Case

| Analysis Type | Guarantees | Over What | |---|---|---| | Worst-case | Every single operation | Any input | | Amortized | Average over ANY sequence | Worst-case sequence | | Average-case | Expected over random inputs | Random distribution |

Amortized O(1) means: any sequence of n operations takes O(n) time total. Individual operations may be expensive, but the expensive ones are rare enough.

This is NOT probabilistic: No randomness is involved. It's a deterministic guarantee about any sequence.

When Amortized Analysis Matters

Amortized O(1) push is fine for most uses of Vec. But if you need every push to be fast (real-time systems), amortized isn't enough — you need worst-case O(1).

Latency-sensitive systems: If a single operation's latency matters (real-time rendering, trading), amortized bounds may be insufficient. Use data structures with worst-case bounds (e.g., finger trees, real-time queues).

Applications in CS

• Dynamic arrays: Vec/ArrayList amortized O(1) push.
• Hash tables: Amortized O(1) insert with resizing.
• Splay trees: Amortized O(log n) without maintaining balance explicitly.
• Union-Find: Near-constant amortized operations.
• Garbage collection: Incremental GC amortizes collection work over allocations.
• Database operations: B-tree split/merge amortized over insertions/deletions.