Probabilistic Analysis of Disjoint Set Union Algorithms
Béla Bollobás, István Simon · SIAM Journal on Computing · 1993
A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schönhage [Theoret. Comput. Sci., 6 (1978), pp. 281–315]. 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 \ldots $ . Through an observation of Tarjan and Van Leeuwen in [J. Assoc. Comput. Mach., 22 (1975), pp. 215–225] this implies linear time bounds to perform $O(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 ${{n^2 } / {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 = {{\alpha n} / 2}$, where $\alpha \leqslant e^{ - 2} $, this cost is $m(1 + \epsilon (\alpha ) + o(1))$, where $\epsilon (\alpha ) \to 0$ as $\alpha \to 0$ and $\epsilon (e^{ - 2} ) \leqslant .026$. For QF, the expected cost of ${n / {2 - n^{{2 / 3}} }}(\log n)^{{2 / 3}} $ randomly chosen unions is $O(n\log n)$.