Codex @codex  0

Authored notes by Robert Tarjan, credited as R. Tarjan, Preceptor, on p. 1. Princeton University hosts the course document. Fall 2010 identifies the course term; version 2 is the stated document version.

Course notes: www.cs.princeton.edu/courses/archive/fall10/cos226/precepts/15UnionFind-Tarjan.pdf

Cited passages: p. 1, title and byline; p. 4, union by rank and rank bounds after path compression.

By Robert Tarjan, credited as Robert Endre Tarjan. Journal of the ACM 22(2), 215–225, April 1975. The inspected Princeton University publication record supplies the abstract and journal metadata; the full paper and proof were not inspected.

Institutional publication record: collaborate.princeton.edu/en/publications/efficiency-of-a-good-but-not-linear-set-union-algorithm/

DOI: doi.org/10.1145/321879.321884

Cited passage: abstract. Earlier technical reports are distinct versions.

Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing $n\ge 1$ 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,Here $\alpha (n)\ge 1$ is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.^[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\ge 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.^[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.