Amortized Analysis
Amortized analysis is a method for analysing the time complexity of a sequence of operations on a data structure by averaging the cost over the entire sequence, even when individual operations may occasionally be expensive. Unlike average-case analysis, amortized analysis provides a worst-case guarantee for the average cost per operation over any sequence of n operations, not just random inputs. The three main methods are the aggregate method (total cost / n), the accounting method (assigning amortized costs with credits), and the potential method (using a potential function to measure stored work).
Key Formula
amortized_cost_i = actual_cost_i + potential(after) - potential(before)
LaTeX: \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})
| Symbol | Meaning | Unit |
|---|---|---|
| \hat{c}_i | Amortized cost of the i-th operation | time units |
| c_i | Actual cost of the i-th operation | time units |
| \Phi(D_i) | Potential of data structure after i-th operation | time units |
| \Phi(D_{i-1}) | Potential of data structure before i-th operation | time units |
Worked Example
Problem
A dynamic array doubles its capacity when full. Starting with capacity 1, perform 8 push operations. Using the aggregate method, what is the amortized cost per push?
Solution
Step 1: Count actual costs. Pushes 1–8 with capacities doubling: push 1 costs 1 (no copy); push 2 costs 1+1=2 (copy 1 element, add 1); push 3 costs 1 (just add); push 4 costs 1+3=4 (copy 3 elements); push 5 costs 1; push 6 costs 1; push 7 costs 1; push 8 costs 1+7=8. Step 2: Total cost = 1+2+1+4+1+1+1+8 = 19 operations. Step 3: Number of pushes = 8. Step 4: Amortized cost = 19/8 ≈ 2.375 per operation.
Answer
Amortized cost per push ≈ O(1) (specifically ≈ 2.375 for 8 operations, bounded by 3 in general)
Amortized Analysis Methods Compared
| Method | Core Idea | Tracks | Suitable For | Example Use |
|---|---|---|---|---|
| Aggregate Method | Total cost / n operations | Running total | Simple, uniform sequences | Dynamic array resizing |
| Accounting Method | Assign amortized costs, bank credits | Credit balance per object | Operations that "save" for future | Stack with multipop |
| Potential Method | Potential function on data structure | Global potential Φ | Complex structures with state | Splay trees, Fibonacci heap |
| Worst-Case per Op | Standard worst-case | Per-operation maximum | Single operations | Hash table lookup |
| Average-Case | Average over input distribution | Probability distribution | Random inputs assumed | Quicksort average case |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
The term "amortized analysis" was introduced by Robert Tarjan in his 1985 paper "Amortized Computational Complexity," borrowing the financial term "amortize" (from Latin "ad mortis," meaning to reduce to nothing or pay off gradually). The concept had been used informally earlier by researchers studying data structures with occasional expensive operations.