Union-Find & Inverse Ackermann

Discover Union-Find with path compression and union by rank, achieving the almost-impossible O(α(n)) bound

Nearly Constant-Time Set Operations

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.

Demo 1: Union-Find Operations

Perform Find and Union operations interactively. Watch how trees form and flatten. Toggle path compression to see its effect on tree structure.

Forest Structure

0
1
2
3
4
5
6
7
8
9

Parent Array

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
Green = root (parent[i] = i)
Disjoint Sets
10
Max Height
1
Max Rank
0

Current Sets

{0}
{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}
{9}

Demo 2: The Ackermann Function

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

The Ackermann Function

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!

Ackermann Values A(m, n)

m \ n012345
0123456
1234567
235791113
35132961125253
4136.6e+4∞∞∞∞
A(2, 2) =
7

Growth Comparison: A(n, n)

nLinear (n)Exponential (2ⁿ)Ackermann A(n,n)
0011
1123
2247
33861
4416∞
5532∞

Inverse Ackermann α(n)

α(n) is the smallest m such that A(m, m) ≥ n. Because Ackermann grows so fast, its inverse grows incredibly slowly:

α(1)
0
α(10)
3
α(1e+3)
4
α(1e+15)
4

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

See A(2, 2) Expansion

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

Demo 3: Path Compression Analysis

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.

16
12

With Compression

Total Path Length
34
Max Path
2

Without Compression

Total Path Length
34
Max Path
2

Operation History

#UnionPath LengthsSets
1(1, 0)1 + 115
2(2, 0)1 + 214
3(3, 0)1 + 213
4(4, 0)1 + 212
5(5, 3)1 + 211
6(6, 0)1 + 210
7(7, 5)1 + 29
8(8, 2)1 + 28
9(9, 2)1 + 27
10(10, 1)1 + 16
11(11, 2)1 + 25
12(12, 2)1 + 24

How Path Compression Works

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.

Demo 4: Real Applications

Union-Find powers Kruskal's MST algorithm (detecting cycles) and connected component detection. See both in action!

Kruskal's Algorithm

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

Step 0 / 11
Edge (0, 3) weight = 5✓ Accept
Connects different components
EdgeWeightStatus
(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 Mastered!

You now understand one of the most practical data structures:

  • Union by rank: attach smaller trees under larger ones
  • Path compression: flatten trees during find operations
  • Ackermann function: grows faster than any primitive recursive function
  • O(α(n)): effectively O(1) for all practical purposes
  • Applications: MST algorithms, connected components, equivalence classes

Next: We'll explore the Fast Fourier Transform — how to multiply polynomials in O(n log n) using roots of unity and the butterfly diagram.