Chapter notes

Many of the important results for disjoint-set data structures are due at least in part to R. E. Tarjan. Using aggregate analysis, Tarjan [290, 292] gave the first tight upper bound in terms of the very slowly growing inverse of Ackermann's function. (The function A_k(j) given in Section 21.4 is similar to Ackermann's function, and the function α(n) is similar to the inverse. Both α(n) and are at most 4 for all conceivable values of m and n.) An O(m lg* n) upper bound was proven earlier by Hopcroft and Ullman [5, 155]. The treatment in Section 21.4 is adapted from a later analysis by Tarjan [294], which is in turn based on an analysis by Kozen [193]. Harfst and Reingold [139] give a potential-based version of Tarjan's earlier bound.

Tarjan and van Leeuwen [295] discuss variants on the path-compression heuristic, including "one-pass methods," which sometimes offer better constant factors in their performance than do two-pass methods. As with Tarjan's earlier analyses of the basic path-compression heuristic, the analyses by Tarjan and van Leeuwen are aggregate. Harfst and Reingold [139] later showed how to make a small change to the potential function to adapt their path-compression analysis to these one-pass variants. Gabow and Tarjan [103] show that in certain applications, the disjoint-set operations can be made to run in O(m) time.

Tarjan [291] showed that a lower bound of time is required for operations on any disjoint-set data structure satisfying certain technical conditions. This lower bound was later generalized by Fredman and Saks [97], who showed that in the worst case, (lg n)-bit words of memory must be accessed.