Chapter notes

| < Day Day Up > |

## 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 Ak(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.

| < Day Day Up > |