The union–find, or disjoint-set union, data structure supports operations such as finding the representative of a set and merging two sets. When path compression is combined with union by rank or size, a sequence of m operations on n elements has an almost constant amortized time bound involving the inverse Ackermann function α(n).
Union–Find Inverse Ackermann Bound
The union–find, or disjoint-set union, data structure supports operations such as finding the representative of a set and merging two sets. When path compression is combined with union by rank or size, a sequence of m operations on n elements has an almost constant amortized time bound involving the inverse Ackermann function α(n).
\(T(m, n) = O(m \alpha(n))\)
What this formula means
Scientific principle
Principle
Union–find maintains a forest of rooted trees representing disjoint sets. Union by rank or size prevents trees from becoming unnecessarily tall, while path compression shortens paths during find operations. Together, these optimizations produce an exceptionally slow-growing inverse Ackermann complexity factor.
Derivation
1. Initially, each of the n elements belongs to its own singleton set.
2. A find operation follows parent pointers until it reaches a representative root.
3. Union by rank or size attaches the root of a smaller or lower-rank tree beneath the larger or higher-rank tree.
4. Path compression changes parent pointers along a find path so that visited nodes point closer to the root.
5. These operations reduce the frequency and cost of future tree traversals.
6. A detailed amortized analysis using the Ackermann hierarchy gives a total operation bound of O(m α(n)) for the standard optimized structure.
7. The inverse Ackermann function grows so slowly that α(n) remains a very small value for all practical input sizes.
Final Result
T(m, n) = O(m α(n))
Amortized Operation Cost
O(α(n))
Inverse Ackermann Relation
α(n) is an extremely slowly growing inverse of an Ackermann-type function.
Optimization Requirements
Path compression
Union by rank or union by size
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
T(m, n) | Total time for a sequence of union–find operations | Abstract operation cost |
m | Total number of find, union, and related operations | Operations |
n | Number of elements in the disjoint-set structure | Elements |
α(n) | Inverse Ackermann function evaluated at n | Dimensionless |
SI units and conversions
Total Cost
Abstract operation count
Operation Count
Operations
Element Count
Elements
Amortized Complexity
O(α(n)) per operation
Conditions of use
The structure represents a collection of disjoint sets.
Path compression is applied during find operations.
Union by rank or union by size is used during merging.
The complexity is amortized across a sequence of operations.
The standard bound is commonly expressed as O(m α(n)) for m operations on n elements.
Limitations and assumptions
The bound is not a constant worst-case guarantee for every individual operation.
A find operation may initially traverse a relatively long path before compression improves it.
The inverse Ackermann bound requires the stated combination of optimizations.
Simpler implementations without path compression or union by rank may have substantially worse complexity.
The exact definition of α(n) varies slightly among mathematical conventions, but these variants have equivalent extremely slow asymptotic growth.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
A disjoint-set structure contains 1,000 elements and performs 10,000 operations. Express the amortized total complexity using the inverse Ackermann bound. |
| The sequence has total complexity O(10,000 α(1,000)), with amortized cost O(α(1,000)) per operation. |
A union–find structure processes 1,000,000 operations on 100,000 elements. Determine its asymptotic total operation bound. |
| The total amortized complexity is O(1,000,000 α(100,000)); the inverse Ackermann factor grows extremely slowly. |
Real-world applications
Connected-component detection
Kruskal's minimum spanning tree algorithm
Network connectivity analysis
Image segmentation
Dynamic equivalence-class management
Formula Meaning
The union–find, or disjoint-set union, data structure supports operations such as finding the representative of a set and merging two sets. When path compression is combined with union by rank or size, a sequence of m operations on n elements has an almost constant amortized time bound involving the inverse Ackermann function α(n).
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.