What is Amortized Analysis?
Learn what amortized analysis is, the three key techniques, and how to explain dynamic array O(1) append in interviews.
Expected Interview Answer
Amortized analysis averages the cost of an operation over a long sequence of operations, guaranteeing that even though some individual calls are expensive, the average cost per call stays bounded — this is why a dynamic array's push_back is called O(1) amortized even though occasional resizes cost O(n).
The three standard techniques are the aggregate method (total cost of n operations divided by n), the accounting method (overcharge cheap operations to prepay for future expensive ones, tracked as stored credit), and the potential method (define a potential function over the data structure and bound cost by actual cost plus the change in potential). Amortized analysis differs from average-case analysis: it makes no assumption about input distribution and holds for every possible sequence of operations, worst case included. Classic examples are dynamic array doubling, the union-find structure with path compression, and incrementing a binary counter. Interviewers care because it explains why code that looks like it does O(n) work per call is still efficient overall.
- Explains why doubling arrays are O(1) amortized
- Gives worst-case-safe bounds, not average-case guesses
- Justifies lazy or batched cleanup strategies
- Underpins union-find, hash table resizing, splay trees
AI Mentor Explanation
A ground staff crew re-rolls and re-marks the pitch fully only once every several matches, not before every single ball. Most balls cost almost nothing in prep time, but the re-marking match costs a lot of staff hours all at once. If you divide total prep hours by total balls bowled across a season, the average per-ball cost is small and predictable. That season-long average, not any single expensive match, is what amortized analysis actually measures.
Step-by-Step Explanation
Step 1
Identify the expensive operation
Find the rare but costly step, such as array resizing or cache rebuilding.
Step 2
Pick a technique
Use aggregate, accounting, or potential method to bound total cost over n operations.
Step 3
Divide total cost by n
The amortized cost per operation is total cost across the whole sequence divided by n.
Step 4
Verify it holds for every sequence
Unlike average-case analysis, the bound must hold for the worst possible sequence, not just typical input.
What Interviewer Expects
- Distinguish amortized analysis from average-case (input-distribution) analysis
- Name at least one of the three techniques: aggregate, accounting, potential method
- Give the dynamic array doubling example with correct reasoning
- Explain why the bound holds for every operation sequence, not just typical ones
Common Mistakes
- Confusing amortized cost with average-case cost over random inputs
- Claiming every individual operation is fast, rather than the average over a sequence
- Forgetting the potential method requires the potential to never go negative
- Not being able to name a real data structure that relies on amortized guarantees
Best Answer (HR Friendly)
“Amortized analysis is a way of proving that even though some operations in a sequence are expensive, the average cost per operation stays low across the whole sequence. It is why we can confidently say adding to a dynamic array is O(1) on average, even though resizing occasionally costs more.”
Code Example
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.data = [None] * self.capacity
def append(self, value):
if self.size == self.capacity:
self.capacity *= 2
new_data = [None] * self.capacity
for i in range(self.size):
new_data[i] = self.data[i]
self.data = new_data
self.data[self.size] = value
self.size += 1
def total_copy_cost(n):
cost = 0
capacity = 1
for i in range(n):
if i == capacity:
cost += capacity
capacity *= 2
return cost # grows linearly in n, so amortized cost per append is O(1)Follow-up Questions
- How does the accounting method assign credit to cheap operations?
- Why is union-find with path compression amortized nearly O(1) per operation?
- How would you prove an amortized bound using the potential method?
- Is amortized O(1) the same guarantee as worst-case O(1)? Why or why not?
MCQ Practice
1. What does amortized analysis guarantee that average-case analysis does not?
Amortized analysis proves a bound over any sequence of operations, independent of input distribution assumptions.
2. Which technique tracks "prepaid credit" on cheap operations to cover future expensive ones?
The accounting method overcharges cheap operations and banks the surplus as credit to pay for later expensive ones.
3. Why is dynamic array append considered O(1) amortized despite occasional O(n) resizes?
Because capacity doubles, the sum of all resize costs across n appends is bounded by O(n), giving O(1) average per append.
Flash Cards
What is amortized analysis? — A method that bounds the average cost per operation over any sequence of operations, not just typical input.
Name the three amortized analysis techniques. — Aggregate method, accounting method, and potential method.
Why is dynamic array append O(1) amortized? — Because doubling capacity means total resize cost across n appends is O(n), averaging to O(1) each.
How does amortized analysis differ from average-case analysis? — Amortized holds for every operation sequence; average-case assumes a distribution over inputs.