On the single-operation worst-case time complexity of the disjoint set union problem.(English)Zbl 0568.68055

Theoretical aspects of computer science, 2nd ann. Symp., Saarbrücken/Ger. 1985, Lect. Notes Comput. Sci. 182, 32-38 (1985).
[For the entire collection see Zbl 0561.00020.]
We give an algorithm for the disjoint set union problem, within the class of algorithms defined by Tarjan, which has O(log n/log log n) single- operation time complexity in the worst-case. Also we define a class of algorithms for the disjoint set union problem, which includes the class of algorithms defined by Tarjan. We prove that any algorithm from this class has at least $$\Omega$$ (log n/log log n) single-operation time complexity in the worst-case.

MSC:

 68R99 Discrete mathematics in relation to computer science 68Q25 Analysis of algorithms and problem complexity

time complexity

Zbl 0561.00020