Amortized Analysis Interview Patterns: Dynamic Arrays, Stack Operations, and Union-Find (2025)

By /
⏱ 6 min read

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 True

Splay 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.

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: LinkedIn Interview Guide

Asked at: Databricks Interview Guide

Scroll to Top