Worst-case Analysis of Set Union Algorithms
Robert Endre Tarjan, Jan Van Leeuwen · Journal of the ACM · 1984
This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union.We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.