Amortized Analysis
Some operations are expensive occasionally but cheap most of the time. If we only look at the worst-case cost per individual operation, we get a pessimistic picture that does not reflect actual performance over a sequence of operations.
Amortized analysis spreads the total cost of a sequence of operations across all of them, giving a more accurate average cost per operation — even when individual operations vary wildly.
Key distinction: amortized ≠ average case. Average case assumes a probability distribution over inputs. Amortized analysis makes no probabilistic assumptions — it is a worst-case guarantee over a sequence of operations.
The Dynamic Array Example
JavaScript arrays (and Python lists, Java ArrayLists) are dynamic — they grow automatically. Internally they use a fixed-capacity buffer. When that buffer fills, the array doubles its capacity and copies all elements into the new buffer.
Most push operations are O(1) — just write to the next slot. But every so often, a push triggers a resize that costs O(n). Does this mean push is O(n)?
class DynamicArray {
constructor() {
this.data = new Array(1); // start with capacity 1
this.size = 0;
this.capacity = 1;
}
push(value) {
if (this.size === this.capacity) {
this._resize(); // expensive! O(n)
}
this.data[this.size] = value;
this.size++;
}
_resize() {
this.capacity *= 2; // double the capacity
const newData = new Array(this.capacity);
for (let i = 0; i < this.size; i++) { // copy all elements
newData[i] = this.data[i]; // O(n) copy
}
this.data = newData;
}
}
// Trace of costs for 8 pushes:
// push(1): capacity=1, size=0 → no resize → cost 1 (total so far: 1)
// push(2): capacity=1, size=1 → RESIZE (copy 1) → cost 1+1=2 (total: 3)
// push(3): capacity=2, size=2 → RESIZE (copy 2) → cost 2+1=3 (total: 6)
// push(4): capacity=4, size=3 → no resize → cost 1 (total: 7)
// push(5): capacity=4, size=4 → RESIZE (copy 4) → cost 4+1=5 (total: 12)
// push(6–8): no resize → cost 1 each (total: 15)
//
// Total cost for 8 pushes = 15 ≈ 2*8 = 16
// Amortized cost per push = 15/8 ≈ 2 = O(1) !After n pushes on a fresh array, the total copy work is: 1 + 2 + 4 + 8 + ... + n/2 + n ≤ 2n
So n push operations cost at most 2n total → amortized O(1) per push. The expensive resizes are rare enough that they average out to constant cost.
Method 1: Aggregate Analysis
The simplest method: compute the total cost of n operations, then divide by n.
For the dynamic array:
- Total copies after n pushes ≤ 2n (geometric series argument)
- Amortized cost per push = 2n / n = O(1)
Aggregate analysis works well when all operations have the same amortized cost.
Method 2: Accounting (Banker) Method
Assign each operation an amortized charge — typically higher than its actual cost. The surplus is stored as "credit" to pay for future expensive operations.
For the dynamic array, charge each push 3 tokens:
- 1 token to pay for writing the element now
- 2 tokens saved as credit (stored with the element)
When a resize copies n elements, each element pays with its 2 saved tokens — covering the 2n copy cost. The account never goes negative, proving amortized O(1) per push.
// Accounting method visualization // Each push deposits 3 tokens. Resize withdraws 2 tokens per element copied. // Capacity doubles from 4 to 8 (copying 4 elements): // Each of the 4 elements has 2 saved tokens → 8 tokens total // Copy cost = 4 → paid by the 8 tokens (with 4 left over) // Why charge 3 and not 2? // - 1 token: write the new element // - 1 token: pay for copying this element in the NEXT resize // - 1 token: pay for copying one OLD element that did NOT save enough credit // (The exact minimum charge is 3 for capacity-doubling arrays)
Method 3: Potential Method
Define a potential function Φ that represents stored energy in the data structure. The amortized cost of operation i is: â_i = actual_cost_i + Φ_i - Φ_{i-1}
For the dynamic array, define: Φ = 2 * size - capacity
- Before resize: Φ = 2n - n = n (size = capacity = n)
- After resize: Φ = 2n - 2n = 0 (capacity doubled to 2n)
For a normal push (no resize):
- actual_cost = 1, Φ increases by 2
- amortized = 1 + 2 = 3 = O(1)
For a push with resize (copying n elements):
- actual_cost = n + 1, Φ drops by n (from n to 0)
- amortized = (n + 1) + (0 - n) = 1 = O(1)
Both cases give O(1) amortized — confirming our result.
Stack with Multipop
Consider a stack that supports three operations: push, pop, and multipop(k) which pops up to k elements. A multipop can be O(n) in the worst case — but what is the amortized cost?
class Stack {
constructor() {
this.items = [];
}
push(x) {
this.items.push(x); // O(1)
}
pop() {
return this.items.pop(); // O(1)
}
multipop(k) {
// Pop up to k elements — O(min(k, size)) work
let count = Math.min(k, this.items.length);
while (count-- > 0) {
this.items.pop();
}
}
}
// Worst case per operation: multipop is O(n)
// But can we call multipop(n) many times? NO!
// Each element can only be POPPED once — it must first be PUSHED.
// In a sequence of n operations, the total pushes ≤ n,
// so the total pops (across ALL multipop calls) ≤ n.
// Total work across n operations = O(n)
// Amortized cost per operation = O(n)/n = O(1)Summary of Methods
Method | Core Idea | Best For |
|---|---|---|
Aggregate | T(n)/n — total cost divided by n operations | All operations have equal amortized cost |
Accounting | Assign amortized charges; prove account stays ≥ 0 | Operations with different amortized costs |
Potential | Φ function captures stored energy; â = actual + ΔΦ | Complex structures with many operation types |
Real-World Implications
JavaScript Array.push() — amortized O(1), occasional O(n) resize is hidden
Java ArrayList.add() — same doubling strategy, amortized O(1)
Hash table insertion — amortized O(1) despite periodic O(n) rehashing
Union-Find with path compression — amortized O(α(n)) per operation (nearly constant)
Splay tree operations — amortized O(log n) per operation despite O(n) worst case
Amortized vs Average Case
// AVERAGE CASE: probabilistic — assumes random inputs // "On average over random inputs, quicksort runs in O(n log n)" // → This says nothing about your specific input // AMORTIZED: deterministic — guarantee over a sequence of operations // "Any sequence of n push operations on a dynamic array runs in O(n) total" // → This is a hard guarantee, no probability involved // Why this matters: // An adversary who knows your algorithm can always trigger worst-case inputs // for average-case analysis. But amortized guarantees hold regardless of input. // Example: std::vector in C++ guarantees amortized O(1) push_back. // Your program will not suddenly become O(n) per push in production.