Discover Union-Find with path compression and union by rank, achieving the almost-impossible O(α(n)) bound
Union-Find keeps track of which items belong together. Two simple tricks make its operations so fast that, for any real input, they are effectively constant time.
Pick x and y, then press Union to merge their sets or Find to walk up to the root. Toggle path compression and watch finds flatten the trees.
The Union-Find (or Disjoint Set Union) data structure maintains a collection of disjoint sets with incredibly fast operations: union two sets, or find which set an element belongs to.
With path compression and union by rank, Union-Find achieves O(α(n)) amortized time per operation, where α is the inverse Ackermann function — a function that grows so slowly it's effectively constant for all practical inputs.
Perform Find and Union operations interactively. Watch how trees form and flatten. Toggle path compression to see its effect on tree structure.
Click cells in the table to see how fast A(m, n) explodes. Its inverse α(n) is at most 4 for any input you could ever store.
A(0, n) = n + 1
A(m, 0) = A(m-1, 1) for m > 0
A(m, n) = A(m-1, A(m, n-1)) for m, n > 0
This recursively-defined function grows faster than any primitive recursive function. A(4, 2) has over 19,000 digits!
| m \ n | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 3 | 5 | 7 | 9 | 11 | 13 |
| 3 | 5 | 13 | 29 | 61 | 125 | 253 |
| 4 | 13 | 6.6e+4 | ∞ | ∞ | ∞ | ∞ |
| n | Linear (n) | Exponential (2ⁿ) | Ackermann A(n,n) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 1 | 1 | 2 | 3 |
| 2 | 2 | 4 | 7 |
| 3 | 3 | 8 | 61 |
| 4 | 4 | 16 | ∞ |
| 5 | 5 | 32 | ∞ |
α(n) is the smallest m such that A(m, m) ≥ n. Because Ackermann grows so fast, its inverse grows incredibly slowly:
For all practical values of n (even 1080 atoms in the universe), α(n) ≤ 4. This is why Union-Find's O(α(n)) is effectively O(1).
A(2, 2) = A(1, A(2, 1))
A(2, 1) = A(1, A(2, 0)) = A(1, A(1, 1)) = A(1, 3) = 5
A(1, 5) = A(0, A(1, 4)) = A(0, A(0, A(1, 3))) = ...
= A(0, A(0, 5)) = A(0, 6) = 7
The Ackermann function A(m, n) grows faster than any primitive recursive function. Its inverse α(n) grows so slowly that α(1080) = 4. This is why O(α(n)) is effectively O(1).
Set the number of elements and unions, then switch path compression on and off. Compare the total path lengths in the two runs.
| # | Union | Path Lengths | Sets |
|---|---|---|---|
| 1 | (1, 0) | 1 + 1 | 15 |
| 2 | (2, 1) | 1 + 1 | 14 |
| 3 | (3, 0) | 1 + 2 | 13 |
| 4 | (4, 3) | 1 + 2 | 12 |
| 5 | (5, 0) | 1 + 2 | 11 |
| 6 | (6, 5) | 1 + 2 | 10 |
| 7 | (7, 6) | 1 + 2 | 9 |
| 8 | (8, 7) | 1 + 2 | 8 |
| 9 | (9, 5) | 1 + 2 | 7 |
| 10 | (10, 4) | 1 + 2 | 6 |
| 11 | (11, 10) | 1 + 2 | 5 |
| 12 | (12, 7) | 1 + 2 | 4 |
During each find(x), path compression makes every node on the path point directly to the root. This flattens the tree, so future operations on these nodes are O(1).
Combined with union by rank, this gives O(α(n)) amortized time per operation, where α is the inverse Ackermann function.
Compare Union-Find with and without path compression. See how compression dramatically reduces total path lengths across a sequence of operations, leading to the O(α(n)) amortized bound.
Step through Kruskal's MST algorithm as it skips edges that would close a cycle, or switch to connected components and click grid cells to reshape the regions.
Sort edges by weight. For each edge, use Union-Find to check if it connects different components. If yes, add to MST. If no, skip (would create cycle).
| Edge | Weight | Status |
|---|---|---|
| (0, 3) | 5 | → |
| (2, 4) | 5 | |
| (3, 5) | 6 | |
| (0, 1) | 7 | |
| (1, 4) | 7 | |
| (1, 2) | 8 | |
| (4, 5) | 8 | |
| (1, 3) | 9 | |
| (4, 6) | 9 | |
| (5, 6) | 11 | |
| (3, 4) | 15 |
Union-Find powers Kruskal's MST algorithm (detecting cycles) and connected component detection. See both in action!
Spot a mistake or have an idea?