Chapter 14+: Amortized Analysis
Vol 2: Algorithm Forest Adventure · Station 14+ (Optional Deep Dive)
Metadata Card
| Attribute | Value |
|---|---|
| Keywords | Amortized Analysis Aggregate Analysis Accounting Method Potential Method Dynamic Array Splay Tree |
Your Progress
Deep in the forest lies an ancient account book recording another kind of wisdom: some operations are occasionally expensive, but averaged over time, they're very cheap.
Breakthrough · Origins
Dynamic Array Resizing
When a Python list appends and runs out of capacity, it allocates 2× space and copies all elements. Single operation cost: O(n). But amortized over n inserts: O(1).
Total cost for n inserts: n + (1 + 2 + 4 + ... + n/2) ≈ 2n. Average = 2.
Three Methods
- Aggregate Analysis: Total cost / number of operations
- Accounting Method: Charge extra for cheap ops, spend credits on expensive ones
- Potential Method: Define a potential function Φ, amortized = actual + ΔΦ
Common Amortized Bounds
| Structure / Operation | Amortized Cost |
|---|---|
| Dynamic array push_back | O(1) |
| Binary counter INCREMENT | O(1) |
| Union-Find find (compression + rank) | O(α(n)) |
| Splay tree search/insert/delete | O(log n) |
Verification Checklist
- [ ] Can explain the difference between amortized O(1) and worst-case O(1)
- [ ] Can analyze dynamic array amortization (aggregate + accounting)
- [ ] Can explain why binary counter increment is amortized O(1)
Traveler's Notes
- Amortized analysis is the answer when someone asks "why is append O(1) when resizing is O(n)?"
- Amortized ≠ Average-case: Amortized bounds make no probabilistic assumptions on input
- The key insight: "Occasionally do heavy work, mostly do light work" is a recurring pattern in CS
→ Next Stop Preview
Chapter 15: Advanced Data Structures