= Union-find operation bounds
{title2=$O(n+m\alpha(n))$}
Assume identifiers, pointers and ranks fit into constant-size <machine words>, with constant-cost indexed <array> access, comparison and assignment. Initializing $n\geq1$ members costs $O(n)$ time and <machine words>. With <union by rank> and full <path compression>, any <sequence> of $m$ <disjoint-set find operations> and <disjoint-set union operations> then has total <time complexity>, in <Big O notation>,
$$
O\bigl(n+m\alpha(n)\bigr).
$$
Here $\alpha(n)\geq1$ is a conventionally normalized <inverse Ackermann function>. The documented path-halving implementation has the same <amortized analysis> bound.<Algorithms, 4th edition by Robert Sedgewick and others/UF.java>[Algorithms, 4th edition by Robert Sedgewick and others; UF.java, class documentation: linear constructor, logarithmic worst-case operations and inverse-Ackermann sequence bound for rank with halving]{ref}
A <disjoint-set union operation> includes two <disjoint-set find operations> and a constant amount of additional linking work. Including $n$ in the bound accounts for initialization even if no queries follow.
This is a bound on an entire <sequence>. It is not a worst-case constant bound for each call: a <disjoint-set find operation> can still encounter a previously uncompressed route of logarithmic length. The <inverse Ackermann function> grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-<sequence> guarantee is explained in <amortized analysis>.
<Robert Tarjan>'s 1975 paper established an <inverse Ackermann function> bound for set union. Its abstract states the sharper two-parameter form for $m\geq n$ representative queries and $n-1$ intermixed merges: the worst total cost is bounded above and below by positive constant multiples of $m\alpha(m,n)$. Those variables count different operations from the convenient $n+m\alpha(n)$ formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.<Efficiency of a Good But Not Linear Set Union Algorithm by Robert Endre Tarjan>[Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM 22(2), April 1975, pp. 215–225, DOI 10.1145/321879.321884; abstract reproduced in Princeton's publication record]{ref}
The intuition is that <union by rank> limits how parent routes grow, while <path compression> makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the <inverse Ackermann function> bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter <rooted tree>. The useful result is that repeated merging and membership queries can share the work of maintaining a changing <partition of a set>.
Back to article page
