Source: CS 225 Lecture, G. Carl Evans | Course: Data Structures, UIUC
Tags: path compression, rank, iterated logarithm, log star, inverse Ackermann, amortised analysis, disjoint sets, CS 225
Difficulty: Intermediate to Advanced | Prerequisites: Part 1 of these notes (disjoint sets structure and union strategies), recursion, amortised analysis basics.
The first set of notes covered how disjoint sets work and how smart union keeps trees at O(log n) height. This second set covers path compression, the optimisation that makes disjoint sets nearly constant time per operation. Together, smart union and path compression bring the amortised cost down to O(α(m,n)) per operation, where α is the inverse Ackermann function, a quantity so small it is ≤ 4 for any input you will ever encounter. This is the analysis that makes union-find one of the most efficient data structures in practice.
Path compression re-wires every node on a find path directly to the root, flattening the tree for future queries. Combined with smart union, this gives an amortised running time of O(m · α(m,n)) for m operations on n elements, which is effectively O(m). The iterated logarithm (log*n) is an intermediate step in the analysis, and the inverse Ackermann function (α) is the final, tightest bound.
Path compression
An optimisation on the find operation: after finding the root, every node along the search path has its parent pointer updated to point directly to the root. Think of it as flattening the branch you just climbed so you never have to climb it again.
Rank
When path compression is combined with union by height, the stored "height" value at a root may no longer equal the true height of the tree (because compression shortens paths without updating the root's counter). The value is therefore called rank: an upper bound on the subtree's height, not necessarily the exact height.
Iterated logarithm (log*n)
The number of times you need to apply the base-2 logarithm to n before the result is 1 or less. Formally: log*(n) = 0 if n ≤ 1, otherwise 1 + log*(log n). This function grows so slowly that log*(2^65536) = 5. For any dataset that fits in a real computer, log*n ≤ 5.
Inverse Ackermann function, α(m,n)
A function that grows even more slowly than log*n. It appears in the tightest known amortised bound for union-find. For all practical purposes, α(m,n) ≤ 4. The proof is well outside CS 225 but the result is expected exam knowledge.
Amortised analysis
A way of averaging the cost of a sequence of operations. Individual operations might occasionally be expensive, but the average cost per operation across the whole sequence is low. In disjoint sets, path compression makes some find calls do extra work (re-pointing nodes), but that work pays off by making future find calls faster.
The basic find follows parent pointers to the root and returns it. Path compression adds one thing: on the way back down (the recursive return), every node visited is re-pointed directly to the root.
int DisjointSets::find(int i) {
if ( s[i] < 0 ) { return i; }
else {
int root = find( s[i] );
s[i] = root; // path compression step
return root;
}
}Before calling find(6) on this tree:
10
/ \
9 11
/ \
1 7
/ \
2 8
/ \
3 4
/ \
5 6After find(6) with path compression, nodes 6, 4, 2, 7, and 9 all point directly to root 10:
10
/ / | | \ \
2 4 9 11 6 7
/ \ | |
3 5 1 8Every node on the path from 6 up to 10 now has 10 as its direct parent. Future calls to find on any of those nodes complete in one step.
Without path compression, union by height tracks the exact height of each tree. Once path compression is introduced, find shortens paths without decrementing the root's height counter. The stored value becomes an upper bound on the true height, no longer exact. We rename it "rank" to make this clear.
Key properties of rank:
A new singleton has rank 0.
When you union two trees, the smaller-rank root becomes a child of the larger-rank root. If ranks are equal, one becomes the child and the other's rank increases by 1.
Path compression never changes any node's rank.
A node of rank k has at least 2^k descendants (same bound as before).
log*n is defined piecewise:
log*(n) = 0, if n ≤ 1
log*(n) = 1 + log*(log₂ n), if n > 1
In words: keep taking the log (base 2) until you hit 1 or less, and count how many times you did it.
Worked example: log*(2^65536)
log(2^65536) = 65536
log(65536) = 16
log(16) = 4
log(4) = 2
log(2) = 1 → stop
That is 5 applications, so log*(2^65536) = 5. For any number of atoms in the observable universe, log*n ≤ 5.
The amortised proof groups non-root nodes into buckets by rank:
Ranks | Bucket |
|---|---|
0 | 0 |
1 | 1 |
2 – 3 | 2 |
4 – 15 | 3 |
16 – 65535 | 4 |
65536 – 2^65536 − 1 | 5 |
Three facts drive the analysis:
The total number of buckets is O(log*n), because each bucket's rank range is an iterated exponential of the previous one.
The maximum number of nodes in any bucket is n divided by the lower bound of the next bucket's rank range.
Within a single find, a node can only be "charged" to its bucket a limited number of times before path compression promotes it out of that bucket (its parent's rank jumps above the bucket ceiling).
With smart union only (no path compression)
Each find is O(log n). A sequence of m operations is O(m log n).
With smart union + path compression
The amortised cost per operation drops dramatically. Two bounds to know:
An intermediate result using the bucket analysis shows O(m · log*n) for m operations. Since log*n ≤ 5 for any practical n, this is effectively O(m).
The tightest known bound is Θ(m · α(m,n)), where α is the inverse Ackermann function. Since α(m,n) ≤ 4 for any conceivable input, this is also effectively O(m).
The key exam answer: any sequence of m union and find operations on a disjoint set with n items, implemented with smart union and path compression, runs in O(m · α(m,n)) time.
Real-world implication
For all practical purposes, each union or find operation takes amortised constant time. This is what makes Kruskal's algorithm so efficient: the union-find operations contribute essentially O(m) to the total cost, where m is the number of edges considered.
Students often think path compression changes the rank stored at the root. It does not. Rank is never decremented; it becomes an upper bound, not the true height.
Students sometimes believe path compression alone is enough for the near-constant bound. You need both path compression and smart union together. Path compression without smart union does not achieve the O(m · α(m,n)) bound.
Students confuse log*n with log(log(n)). log*n counts how many times you apply log until you reach 1. log(log(n)) applies log exactly twice. For n = 2^65536, log(log(n)) = 16, but log*n = 5.
Students assume α(m,n) is always 1 or that it equals log*n. α grows slower than log*; for practical n, α(m,n) ≤ 4, but it is a distinct function.
⚠️ Be able to trace a find call with path compression: draw the tree before and after, showing which nodes get re-pointed.
⚠️ Know the final amortised bound: O(m · α(m,n)) for m operations. Fill-in-the-blank questions love this.
⚠️ Know what log*n is, and be able to compute it for small values (e.g., log*(2^65536) = 5).
⚠️ Understand that rank ≠ true height once path compression is in play.
⚠️ The bucket table (ranks → bucket numbers) may appear as a "fill in the table" question.
True or false: path compression changes the rank stored at the root. False.
Fill in the blank: log*(2^65536) = ______. 5.
True or false: with smart union and path compression, a single find operation is guaranteed O(1). False (the amortised cost is nearly constant, but a single worst-case find can still be O(log n)).
Fill in the blank: the tightest amortised bound for m union/find operations is O(m · ______). α(m,n).
True or false: path compression without smart union achieves the same amortised bound. False.
Q: After calling find(6) with path compression on the example tree (root 10, path 6→4→2→7→9→10), which nodes now point directly to 10?
A: Nodes 6, 4, 2, 7, and 9 all have their parent set to 10.
Q: What is the difference between "rank" and "height" in a disjoint set with path compression?
A: Height is the exact longest path from root to leaf. Rank is an upper bound on height that was accurate before path compression but is never decremented when compression shortens paths. Once compression is active, rank ≥ true height.
Q: Compute log*(65536).
A: log(65536) = 16 → log(16) = 4 → log(4) = 2 → log(2) = 1 → stop. That is 4 applications, so log*(65536) = 4.
Q: What is the worst-case running time of m union and find operations on n elements with smart union and path compression?
A: O(m · α(m,n)), where α is the inverse Ackermann function.
Q: A disjoint set uses union by rank. Two roots both have rank 3. After unioning them, what is the new root's rank?
A: 4. When ranks are equal, the new root's rank increases by 1.
Path compression is an example of a "lazy" optimisation: you do a small amount of extra work now to save a large amount later. The same idea appears in splay trees (restructuring on access) and in caching. The amortised analysis technique, using a potential function or an accounting argument to average costs over a sequence of operations, also appears in the analysis of dynamic arrays (doubling strategy) and hash table resizing.
path compression, union by rank, rank vs height, iterated logarithm, log star, log*n, inverse Ackermann function, alpha function, amortised analysis, union-find optimisation, disjoint sets analysis, near-constant time, Kruskal's algorithm, connected components, CS 225, UIUC, data structures, bucket analysis, potential function