next up previous
Next: An Implementation of the Up: Abstracts Previous: On the single-operation worst-case

A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals

We define a class of algorithms for the disjoint set union problem on intervals that includes the class of pointer-algorithms defined by Tarjan. We show that each algorithm from this class has at least $\Omega(\log n / \log \log n)$ single-operation worst-case time complexity. The proof is based on a modification of the proof for the general union-find problem in Blum (1986).

Claus Rick