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 Ω (log n / log log n) single-operation time complexity in the worst case.
No takes yet. Share an insight, caveat, or question.
Norbert Blüm (1986) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: