The Potential Function Behind the Inverse-Ackermann Union-Find Bound

Kruskal’s algorithm, percolation testing, and unification in a type checker all run on the same primitive: maintain a partition of n elements under two operations, find which set an element belongs to and merge two sets. A naive implementation has one of the two operations costing Θ(n). The standard implementation, a forest of parent pointers with path compression and union by rank, achieves O(m α(n)) amortized time for m operations, where α is the inverse of the Ackermann function and grows so slowly that α(n) ≤ 4 for any n that can be written in the physical universe. The bound is not derived by finding the worst tree shape, because there is no set of trees that achieves it; it is derived by charging every find operation against a per-node potential that is exhausted only logarithmically many times.

The two policies and what each fixes

Each set is a rooted tree; the root is the set’s representative. The parent array gives each node a parent (the root points to itself). find(x) walks parent pointers to the root. union(x, y) links one root under the other. The naive forest, link either root, walk to the root on every query, can degrade into a chain of length n. A union that always links the root of the first set under the second builds a path of length n after n unions, and a single find then costs Θ(n). Two ideas repair this, and they interact in a way that makes the analysis hard. Union by rank stores a rank per node, initially 0, which increases by one when a node becomes the parent of another node with equal rank. Linking the lower-rank root under the higher-rank one keeps every tree’s height at most log₂ n, because a tree of height h has at least 2^h nodes: the rank bounds the height by induction, and a root’s rank only increases when two equal-rank trees merge. With union by rank alone, both operations are O(log n) worst case, and the bound needs no averaging. Path compression points every node on a find path directly at the root. A find that walks a path of length k rewrites k − 1 pointers to reach the root, so the same path is short on the next query. Path compression changes the structure in ways that no simple height invariant covers, because the rewrite shortens subtrees whose rank was already fixed. With path compression alone, and arbitrary unions, the amortized bound is Θ(log n), not constant: the compression work is real, and a sequence of unions that builds tall trees repeatedly forces long compressions, though the total is still Θ(m log n) for m operations rather than Θ(mn).

The accounting that produces α(n)

The classical proof, due to Tarjan, assigns each node a rank and then a level derived from a function of the rank and the number of finds performed so far. The mechanism rests on two facts about path compression. The first is that compression never increases any node’s rank or the rank of any parent, and never creates a parent with lower rank than its child. The rank of a node is fixed once it stops being a root, and it can only increase while the node is a root. Rank is thus a monotonically non-decreasing label, and a node’s rank never exceeds ⌊log₂ n⌋. The second fact is the one that makes the accounting work. Consider a node v whose parent is p. Between two consecutive finds that pass through v, the rank of v’s parent strictly increases. When a find compresses v, it sets parent[v] to the root, whose rank is greater than or equal to the rank of the old parent. If a later find passes through v again, the path was rebuilt under v by the growth of the tree above it, and the new parent has strictly greater rank than the old one, because only linking can insert new nodes between v and the root. Since rank is bounded by log₂ n, a node can be compressed only O(log n) times as a non-root, because each compression of that node requires its parent’s rank to have increased, and rank is bounded by ⌊log₂ n⌋. The refinement is to divide the range of ranks into blocks and count how many times a node’s parent rank crosses a block boundary. The boundaries follow the Ackermann hierarchy rather than a single exponential: block k ends at rank A(k, 4). Because those boundaries outgrow every fixed tower of exponentials, only α(n) of them lie below log₂ n, and a node’s parent can cross each one at most once, so a node accumulates at most α(n) crossings before its parent’s rank reaches log₂ n. The compressions that stay inside the topmost block are charged to the finds that cause them. Summed over all nodes, and with the rank increases charged separately, the total is O(m α(n)). $$\alpha(n) = \min{,k : A(k, 4) \ge \lceil \log_2 n \rceil,}$$ The purely mathematical content is the size of α. The Ackermann function A(k, j) grows by iterated application: A(0, j) = j + 1, A(k, 0) = A(k−1, 1), and A(k, j) = A(k−1, A(k, j−1)). Evaluating α(n) for any n that could be written inside a computer’s memory gives a value at most 4. The bound is therefore effectively constant for every practical n, but it is not a constant in the strict sense: it grows without bound as n does, which is the technical difference between “linear” and “not quite linear”.

Why the bound is essentially the best possible

For a long time it was open whether the α(n) term could be removed, and the answer is that it cannot for pointer machines whose algorithms treat the elements individually: Tarjan and van Leeuwen showed that every such implementation of the disjoint-set problem must spend Ω(m α(n)) time on some sequence of m operations. Within that class the union-by-rank plus path-compression algorithm is optimal up to a constant factor, not merely a good heuristic. The gap is closed in a different model. Gabow and Tarjan showed that when the sequence of unions is known in advance and the elements can be numbered so that each set being merged is an interval, the problem becomes linear. That precondition holds for some offline connectivity problems on graphs whose vertices admit such a numbering, and it does not hold in general. The distinction is worth keeping in mind when a statement claims “linear-time union-find”: it is linear under a restriction on the operations, not as a general result.

Implementation and the details that change constants

The implementation is small. The parent array holds 32-bit or 64-bit indices, the rank array can be packed into a byte when n is below 2^255, and the two operations are loops.

pub struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<u32>,
}
impl DisjointSet {
    pub fn new(n: usize) -> Self {
        DisjointSet { parent: (0..n).collect(), rank: vec![0; n] }
    }
    pub fn find(&mut self, mut x: usize) -> usize {
        let mut root = x;
        while self.parent[root] != root {
            root = self.parent[root];
        }
        while self.parent[x] != root {
            let next = self.parent[x];
            self.parent[x] = root;       // compress the path as we walk back
            x = next;
        }
        root
    }
    pub fn union(&mut self, a: usize, b: usize) -> bool {
        let (mut ra, mut rb) = (self.find(a), self.find(b));
        if ra == rb {
            return false;                // already in the same set
        }
        if self.rank[ra] < self.rank[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        self.parent[rb] = ra;
        if self.rank[ra] == self.rank[rb] {
            self.rank[ra] += 1;          // rank grows only on a tie
        }
        true
    }
}

Iterative find avoids the stack overflow that a recursive version risks on a deep initial path, and it performs two passes rather than the recursive version’s single pass followed by unwinding; the two-pass form touches the path twice in exchange for avoiding call overhead. Path halving, pointing every other node at its grandparent, is an alternative that compresses only partially and writes half as many pointers per find. Path compression can be dropped entirely if the cost of the extra writes is unacceptable and the operation count is small. Union by rank alone gives O(log n) worst case with no compression writes, which can be the better choice for very short-running programs, since the α(n) bound carries a larger constant. Conversely, if unions are known before any finds, as in an offline algorithm that builds the structure bottom-up, the union-by-size policy with no compression and a pre-built shallow tree can be cheaper than applying compression at query time. Two implementation details change correctness rather than cost. Path compression must not be applied while the union operation is midway through linking roots, or a root can be rewritten under a find that is still using it; in a concurrent setting this is the entire difficulty, and lock-free disjoint sets use atomic compare-and-swap on the parent array with compression applied only when the swap succeeds. And rank must not be decremented anywhere: a node that has become a non-root keeps its rank forever, and treating rank as “current height” is the classic bug that silently degrades the structure to a linked list.

Where the structure appears in a larger complexity argument

Disjoint sets are rarely the whole algorithm; they are a component whose cost is added to something else. Kruskal’s algorithm sorts m edges, Θ(m log m), then processes them in order with 2m finds and at most n − 1 unions. The disjoint-set work is O(m α(n)), which is swallowed by the sort, and the total is Θ(m log m), the same bound as a comparison sort of the edge list, with the union-find structure contributing a term that never dominates. This is a case where the fancy bound is invisible in the final result, and it is worth knowing that the α(n) machinery exists for the sake of the structure; the algorithm would achieve the same total with a plain O(log n) union-find. The same is not true of offline connectivity and incremental cycle detection, where the number of union-find operations is large relative to any sorting, and the α(n) term is the difference between linear and n log n overall. The technique, charge each operation to a monotonically increasing quantity on some element, bound how often that quantity increases, and note that the number of distinct values is small because the range is tiny, recurs throughout amortized analysis. It is the same shape as the potential argument for dynamic arrays, generalized from a single scalar potential to a per-element rank, and the same limitation applies: the bound is about the sequence, and a single find in the middle of it can cost Θ(log n) walking a cold path. A structure that must bound every individual operation rather than the average needs a different design, and expected-cost arguments are usually what replaces the amortized form once old versions must remain intact.