×

zbMATH — the first resource for mathematics

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
Keywords:
time complexity