Amortized Analysis and Time Complexity Patterns
Amortized analysis evaluates the average performance of operations over a sequence, not worst-case per operation. It is essential for understanding dynamic arrays, hash tables, and Union-Find, and comes up in senior-level algorithm interviews at companies like Google, Meta, and Jane Street.
What is Amortized Analysis?
Some data structures have operations that are occasionally expensive but rarely so. If we charge the expensive operation against the cheap operations that preceded it, the amortized cost per operation is still O(1).
Three methods: Aggregate (total cost / n), Accounting (virtual credits), Potential (mathematical potential function). For interviews, understand the intuition — you rarely need to prove the formal bound.
Dynamic Array (ArrayList / Python List)
A dynamic array doubles in capacity when full. Individual appends: mostly O(1), occasionally O(n) when resizing. Why is append O(1) amortized?
Capacity 1 → fill → resize to 2 (copy 1 element)
Capacity 2 → fill → resize to 4 (copy 2 elements)
Capacity 4 → fill → resize to 8 (copy 4 elements)
...
After n appends: copies = 1 + 2 + 4 + ... + n/2 = n-1
Total work for n appends = n (the appends) + n-1 (copies) = 2n-1 = O(n)
Amortized cost per append = O(n)/n = O(1)The doubling strategy is critical — growing by a fixed amount (e.g., +10) would give O(n^2) total, O(n) amortized. Doubling gives O(n) total, O(1) amortized.
Hash Table
Hash tables resize (rehash) when the load factor exceeds a threshold (typically 0.75). Rehashing is O(n) but rare. Amortized cost of insert is O(1) by the same argument as dynamic array doubling.
Collision resolution:
- Chaining: each bucket is a linked list. Worst case O(n) if all keys hash to one bucket. Expected O(1) with a good hash function and load factor < 1.
- Open addressing: probe for the next empty slot. Better cache performance, but degrades faster at high load factors. Python dicts use open addressing.
Union-Find (Disjoint Set Union)
Union-Find supports: find(x) — return the root of x's set; union(x, y) — merge the sets containing x and y.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return TrueWith path compression + union by rank: amortized O(α(n)) per operation, where α is the inverse Ackermann function — effectively O(1) for all practical inputs (α(n) ≤ 4 for n < 10^600).
Stack with O(1) Min (LeetCode 155)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # tracks current min at each depth
def push(self, val):
self.stack.append(val)
cur_min = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(cur_min)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def get_min(self): return self.min_stack[-1]Sliding Window Maximum (Monotonic Deque)
Finding the max of every window of size k in O(n) using a deque that maintains a decreasing order:
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values are decreasing
result = []
for i, n in enumerate(nums):
# Remove elements outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements (they can never be max)
while dq and nums[dq[-1]] = k - 1:
result.append(nums[dq[0]])
return result
# Each element is added and removed at most once: O(n) totalAmortized analysis: each index enters and leaves the deque exactly once, so total operations = 2n = O(n) across all windows.
Two-Stack Queue (Amortized O(1) enqueue/dequeue)
class MyQueue:
def __init__(self):
self.inbox = [] # receives new elements
self.outbox = [] # serves dequeue requests
def enqueue(self, val): self.inbox.append(val)
def dequeue(self):
if not self.outbox:
while self.inbox: # transfer all: O(n) but rare
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
# Each element crosses from inbox to outbox exactly once: O(1) amortizedCommon Complexity Patterns
| Pattern | Worst case per op | Amortized |
|---|---|---|
| Dynamic array append | O(n) | O(1) |
| Hash table insert | O(n) | O(1) |
| Union-Find (with optimizations) | O(log n) | O(α(n)) ≈ O(1) |
| Monotonic deque window | O(n) | O(1) per element |
| Two-stack queue dequeue | O(n) | O(1) |
| Splay tree operation | O(n) | O(log n) |
Interview Tips
- When an interviewer asks “but isn't resize O(n)?” — explain amortized analysis with the doubling argument
- Union-Find comes up in graph problems: number of islands, redundant connection, accounts merge
- Monotonic deque is the key to any sliding window maximum/minimum problem in O(n)
- Two-stack queue is a classic question at Google, Apple, and Microsoft
- For Union-Find, always implement both path compression and union by rank — missing either gives a weaker bound
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why is dynamic array append O(1) amortized despite occasional O(n) resizes?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “When a dynamic array doubles in capacity, it copies all n elements — O(n). But consider the full sequence of n appends. Copies happen at sizes 1, 2, 4, 8, … n/2: total copies = 1+2+4+…+n/2 = n-1. So n appends require n operations plus n-1 copies = 2n-1 total work = O(n). Dividing by n appends: O(1) amortized. The key is doubling — each element is copied at most once per doubling, and doublings happen O(log n) times. Growing by a fixed amount instead would give O(n) amortized (O(n^2) total), which is why Python list, Java ArrayList, and C++ vector all use geometric growth.” }
},
{
“@type”: “Question”,
“name”: “How does path compression make Union-Find nearly O(1)?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Without optimizations, Union-Find trees can degrade to O(n) depth. Path compression flattens the tree during find(): when traversing to the root, make every visited node point directly to the root. Union by rank prevents tall trees by always attaching the shorter tree under the taller one. Together, these give amortized O(alpha(n)) per operation, where alpha is the inverse Ackermann function — for all inputs in the physical universe, alpha(n) <= 4. In practice this means Union-Find is effectively O(1) per operation. It is the standard tool for: connected components, cycle detection in undirected graphs, Kruskal MST, and accounts merge problems.” }
},
{
“@type”: “Question”,
“name”: “What is a monotonic deque and when should you use it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “A monotonic deque maintains elements in sorted order (increasing or decreasing) by removing elements from the back that violate the ordering before adding a new element. For sliding window maximum: maintain a decreasing deque of indices. For each new element, pop from back while the back element is smaller (it can never be max). Pop from front when outside the window. The front always holds the current window maximum. Amortized O(1) per element because each index is added and removed at most once. Use cases: sliding window max/min (LeetCode 239), largest rectangle in histogram, daily temperatures (monotonic stack variant).” }
}
]
}