All Roadmaps›🧠 Data Structures & Algorithms›Phase 1›Amortized Analysis

Amortized Analysis

0/12 in this phase0/57 across the roadmap

📖 Concept

Amortized analysis looks at the average cost per operation over a sequence of operations, rather than the worst case of any single operation. Some operations are expensive occasionally but cheap most of the time.

Why it matters: Without amortized analysis, you'd think Array.push() is inefficient (because it sometimes needs to resize). In reality, it's O(1) amortized — the occasional O(n) resize is spread across all the cheap O(1) pushes.

Key examples:

1. Dynamic Array (JavaScript Array / ArrayList):

  • Push is usually O(1) — just add to the end
  • When full, the array doubles in size — this single push is O(n) (copy all elements)
  • But doubling happens rarely: after 1, 2, 4, 8, 16... pushes
  • Total cost for n pushes: n + n/2 + n/4 + ... ≈ 2n → O(1) amortized per push

2. Hash Table Rehashing:

  • Insert is usually O(1)
  • When load factor exceeds threshold, rehash all elements — O(n)
  • Happens rarely enough that amortized cost is still O(1)

3. Stack with multipop:

  • pop() is O(1), but multipop(k) removes k elements — O(k)
  • Over n operations total, each element is pushed and popped at most once
  • Amortized: O(1) per operation

Methods of amortized analysis:

  1. Aggregate method: Total cost / number of operations
  2. Accounting method: Assign "credits" to cheap operations to pay for expensive ones
  3. Potential method: Define a potential function that captures saved-up work

🏠 Real-world analogy: Car insurance. Most months you pay a small premium (O(1)). One accident costs a lot (O(n)). But spread over years, the average monthly cost is still manageable — that's amortized cost.

💻 Code Example

codeTap to expand ⛶
1// DYNAMIC ARRAY — Why push() is O(1) amortized
2class DynamicArray {
3  constructor() {
4    this.data = new Array(2);  // Start with capacity 2
5    this.length = 0;
6    this.capacity = 2;
7  }
8

9  push(value) {
10    if (this.length === this.capacity) {
11      this._resize();  // O(n) — but happens rarely!
12    }
13    this.data[this.length] = value;  // O(1) — happens every time
14    this.length++;
15  }
16

17  _resize() {
18    this.capacity *= 2;  // Double the capacity
19    const newData = new Array(this.capacity);
20    for (let i = 0; i < this.length; i++) {
21      newData[i] = this.data[i];  // Copy all elements — O(n)
22    }
23    this.data = newData;
24    console.log(`Resized to ${this.capacity}`);
25  }
26}
27

28// Demonstration: push 16 elements
29const arr = new DynamicArray();
30for (let i = 0; i < 16; i++) {
31  arr.push(i);
32}
33// Resizes at: 2→4 (copy 2), 4→8 (copy 4), 8→16 (copy 8)
34// Total copies: 2 + 4 + 8 = 14 for 16 pushes
35// Amortized: ~1 copy per push → O(1)
36

37// TypeScript version
38class DynamicArrayTS<T> {
39  private data: (T | undefined)[];
40  private _length: number = 0;
41  private capacity: number;
42

43  constructor(initialCapacity: number = 2) {
44    this.capacity = initialCapacity;
45    this.data = new Array(this.capacity);
46  }
47

48  push(value: T): void {
49    if (this._length === this.capacity) {
50      this.resize();
51    }
52    this.data[this._length] = value;
53    this._length++;
54  }
55

56  private resize(): void {
57    this.capacity *= 2;
58    const newData: (T | undefined)[] = new Array(this.capacity);
59    for (let i = 0; i < this._length; i++) {
60      newData[i] = this.data[i];
61    }
62    this.data = newData;
63  }
64

65  get length(): number { return this._length; }
66}
67

68// ACCOUNTING METHOD INTUITION
69// Each push "pays" 3 coins:
70//   1 coin: for the push itself
71//   2 coins: saved for future resize
72// When resize happens (copy n elements),
73// the n saved coins pay for it exactly.
74// Result: each push costs 3 → O(1) amortized

🏋️ Practice Exercise

Practice Problems:

  1. If a dynamic array starts at size 1 and doubles, how many total copies after 32 pushes?
  2. What if the array triples instead of doubles? Still O(1) amortized?
  3. Why is it BAD to grow by a constant (e.g., add 10 slots each time)?
  4. Explain why JavaScript's Array.push() is O(1) amortized
  5. A stack supports push, pop, and multipop(k). Prove multipop is O(1) amortized
  6. Hash table with load factor 0.75 resizes by 2x. What's amortized insert cost?
  7. What would happen to amortized cost if we shrink the array when it's only 1/4 full?
  8. Compare: ArrayList.add() in Java vs linked list append — amortized costs
  9. Why doesn't pop() on a dynamic array ever need to resize?
  10. Design a queue using two stacks — what's the amortized dequeue time?

⚠️ Common Mistakes

  • Confusing amortized with average case — amortized is a GUARANTEE over any sequence, not a probabilistic average

  • Thinking O(1) amortized means every operation is O(1) — some individual operations CAN be O(n), but they're rare enough

  • Not understanding the doubling strategy — growing by a fixed amount (e.g., +10) gives O(n) amortized, not O(1)

  • Applying amortized analysis to single operations — it only makes sense over a SEQUENCE of operations

  • Forgetting that amortized O(1) doesn't help with real-time systems — a single O(n) resize can cause a latency spike

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Amortized Analysis

← PreviousBest / Worst / Average Case AnalysisNext →Recursion Fundamentals