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.

A computer scientist whose work with Robert Tarjan includes splay trees and amortized analysis. His Carnegie Mellon University homepage identifies his full name and academic role.^[ref]

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.

Michael L. Fredman co-developed Fibonacci heaps with Robert Tarjan. Their 1987 paper uses deferred restructuring and amortized analysis to obtain constant amortized time for operations including insertion and decrease-key, with logarithmic amortized time for delete-min.^[ref]

This matters in graph algorithms that repeatedly lower tentative priorities: reducing the cost of many decrease-key operations can improve a whole algorithm's bound. A single operation can still be expensive. The guarantee concerns the total cost of a sequence, so confusing amortized time with the worst-case analysis of each individual operation loses the point of the construction.

Robert Tarjan is a computer scientist whose work connects efficient graph algorithms, data structures and rigorous analysis. His contributions include algorithms for lowest common ancestors and, with collaborators, splay trees and Fibonacci heaps.^[ref]

His work on amortized analysis explains why an individual operation can be expensive while a whole sequence remains efficient. The accounting assigns the cost of occasional restructuring across the sequence instead of assuming each operation has the same worst-case cost. Splay trees make this distinction particularly concrete: moving recently accessed nodes changes the tree while supporting strong bounds over a sequence of accesses.^[ref]

Homepage: www.cs.princeton.edu/~ret/

Institutional profile: www.hertzfoundation.org/people/robert-tarjan/

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.