What Is Amortized Analysis?
Amortized analysis gives the average cost per operation over a sequence of operations, even when individual operations can be expensive. It is different from average-case analysis (which averages over random inputs). Amortized analysis considers the worst-case sequence of operations and shows the average cost per operation in that sequence. Three methods: aggregate (total cost / n operations), accounting (assign credits to cheap operations to pay for future expensive ones), potential (use a potential function to measure stored energy). The result: O(1) amortized even if some operations are O(n).
Dynamic Array (ArrayList) Doubling
A dynamic array doubles capacity when full. Most appends are O(1). When the array doubles (size n): copying n elements costs O(n). Amortized analysis with aggregate method: n appends with k doublings (k = log n). Total work: n (appends) + 1 + 2 + 4 + … + n (copy costs) = n + 2n = 3n = O(n). Per operation: O(n)/n = O(1) amortized. Accounting method intuition: charge each append 3 tokens. 1 token pays for the append itself. 2 tokens are saved. When the array doubles, the n/2 new elements each have 2 saved tokens, providing n tokens to pay for copying n elements. Each token was charged to an original append.
Stack with Multi-Pop
A stack supports PUSH, POP, and MULTIPOP(k) (pop min(k, stack_size) elements). Individual MULTIPOP can cost O(n). Amortized analysis: each element can be pushed and popped at most once. Total operations on n pushes: n pushes + at most n pops total (across all POPs and MULTIPOPs) = 2n = O(n). Amortized cost per operation: O(n) / n = O(1). Accounting: charge PUSH 2 tokens. 1 pays for the push itself. 1 is saved on the element. POP/MULTIPOP costs 1 token per element popped — paid by the saved token on each element. MULTIPOPs always have enough saved tokens to pay for themselves.
Union-Find with Path Compression and Union by Rank
Union-Find (Disjoint Set Union): find(x) returns the root of x set. union(x,y) merges the sets. Without optimizations: O(n) per operation. Union by rank: always attach the smaller tree under the root of the larger tree. This limits tree height to O(log n). Path compression: on find(x), make every node on the path point directly to the root (flattening the tree for future queries). Combined: amortized O(alpha(n)) per operation, where alpha is the inverse Ackermann function — effectively O(1) for any practical n. Proof uses the potential method with a complex potential function based on rank and path lengths — cite the result in interviews without re-deriving.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return False
if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
self.parent[ry] = rx # union by rank
if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
return TrueSplay Trees
Splay trees are a self-adjusting BST where each access rotates the accessed node to the root (splay operation). Individual accesses can be O(n). Amortized O(log n) using the potential method: Phi = sum of log(size(node)) for all nodes. An access to a deep node restructures the tree, decreasing the potential significantly. The amortized cost = actual cost + delta(Phi) = O(log n). Splay trees have optimal working set property: accessing the same element k times in a row costs O(k + log n) rather than O(k log n). Used when access patterns exhibit temporal locality.
Interview Tips
- For dynamic arrays: say “O(1) amortized” and explain the doubling argument in terms of credit per push.
- Union-Find: state O(alpha(n)) and note it is effectively O(1). Show path compression + union by rank code.
- The accounting method intuition: prepay for expensive future operations with cheap current operations.
- Amortized analysis only applies to sequences — a single MULTIPOP is still O(n) in isolation.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What does amortized O(1) mean for dynamic array append?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Amortized O(1) means that while a single append can take O(n) time (when the array doubles and copies n elements), the average cost over a sequence of n appends is O(1) per append. The key insight: the expensive doubling operation happens rarely (after 1, 2, 4, 8, … appends). Total work for n appends: n appends each cost 1, plus copying costs 1+2+4+…+n/2 = n-1. Total = 2n-1 = O(n). Divided by n appends: O(1) per operation. You can think of it as prepaying: each cheap append pays 1 token for itself and saves 1 token for the future doubling. When the array doubles, there are exactly enough saved tokens to pay for the copy.”
}
},
{
“@type”: “Question”,
“name”: “How does path compression improve Union-Find performance?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Without path compression, find(x) traverses the chain from x to the root — O(tree height). With union by rank alone: height is O(log n). Path compression flattens the tree: after find(x) reaches the root, every node on the path is updated to point directly to the root. Future find operations on those nodes skip directly to the root. Combined with union by rank, the amortized cost per operation is O(alpha(n)), where alpha is the inverse Ackermann function — slower than O(1) but faster than O(log* n) and effectively constant for any n that fits in the universe. Two-pass path compression: first pass finds the root; second pass updates all pointers. Path halving (simpler): only update every other node, achieving the same asymptotic bound.”
}
},
{
“@type”: “Question”,
“name”: “What is the accounting method in amortized analysis?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The accounting method assigns an amortized cost to each operation, which may differ from the actual cost. Cheap operations are charged more than their actual cost; the overcharge is stored as credit. Expensive operations are charged less than their actual cost; the deficit is paid from accumulated credit. Rule: total amortized cost >= total actual cost (credit never goes negative). Example for dynamic array: charge each append 3 tokens. Actual cost = 1 (the append). Savings = 2. When the array of size n doubles: n/2 new elements each have 2 saved tokens = n total credits. The copy costs n = covered exactly. Amortized cost = 3 per append, actual total = O(n). This is tighter than the aggregate method and makes the credit flow explicit.”
}
},
{
“@type”: “Question”,
“name”: “How does Union-Find with union by rank prevent degenerate trees?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Without optimization, repeated union(0,1), union(1,2), union(2,3)… creates a linked list of height n, making find O(n). Union by rank prevents this: each tree has a rank (an upper bound on height). When unioning two trees: attach the tree with smaller rank under the root of the larger rank tree. If ranks are equal: attach either way and increment the root rank. Key invariant: a tree of rank r has at least 2^r nodes. So rank is at most log n. This limits tree height to O(log n) for find operations without path compression. With both path compression and union by rank: O(alpha(n)) amortized. Never use union by size vs rank interchangeably — both give O(log n) without compression, but union by rank has a cleaner theoretical analysis.”
}
},
{
“@type”: “Question”,
“name”: “What is the potential method in amortized analysis?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The potential method defines a potential function Phi mapping data structure states to real numbers (like potential energy). Amortized cost of operation i = actual cost + Phi(state after) – Phi(state before). The sum of amortized costs = sum of actual costs + Phi(final) – Phi(initial). If Phi(final) >= Phi(initial): amortized cost >= actual cost (conservative bound). For dynamic arrays: Phi = 2*(current_size – capacity/2) = number of elements in the second half of the array. Phi increases by 2 on each non-doubling append (cheap). Phi drops to 0 on doubling (all elements are now in the first half of the doubled array). The amortized cost of doubling = actual cost n + Phi(after) – Phi(before) = n + 0 – n = 0. Amortized cost of regular append = 1 + 2 = 3. This matches the accounting method result.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Databricks Interview Guide