PROBABILISTIC ANALYSIS OF DISJOINT SET UNION ALGORITHMS

A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schonhage [Theoret. Comput. Sci., 6 (1978), pp. 281-3151. This paper shows that the expected time of the Weighted Quick-Find (QFW) algorithm to perform (n - 1) randomly chosen unions is cn + o (n / log n), where c = 2.0847 .... Through an observation of Tarjan and Van Leeuwen in V. Assoc. Comput. Mach., 22 (1975), pp. 215-2251 this implies linear time bounds to perform 0(n) unions and finds for a class of other union-find algorithms. It is also proved that the expected time of the Unweighted Quick-Find (QF) algorithm is n2/8 + O(n(log n)2). The expected costs of QFW and QF are analyzed when fewer than (n - 1) unions are performed. Among other results, for QFW it is shown that the expected cost of m = o(n) randomly chosen unions is m(1 + o(1)). If m = alphan/2, where alpha less-than-or-equal-to e-2, this cost is m(1 + epsilon(alpha) + o(1)), where epsilon(alpha) --> 0 as a --> 0 and epsilon(e-2) less-than-or-equal-to .026. For QF, the expected cost of n/2 - n2/3(log n)2/3 randomly chosen unions is 0(n log n).