A LOWER-BOUND ON THE SINGLE-OPERATION WORST-CASE TIME-COMPLEXITY OF THE UNION-FIND PROBLEM ON INTERVALS

Authors
BLUM N ROCHOW H
Citation
N. Blum et H. Rochow, A LOWER-BOUND ON THE SINGLE-OPERATION WORST-CASE TIME-COMPLEXITY OF THE UNION-FIND PROBLEM ON INTERVALS, Information processing letters, 51(2), 1994, pp. 57-60
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
51
Issue
2
Year of publication
1994
Pages
57 - 60
Database
ISI
SICI code
0020-0190(1994)51:2<57:ALOTSW>2.0.ZU;2-S
Abstract
We define a class of algorithms for the disjoint set union problem on intervals that includes the class 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 i s based on a modification of the proof for the general union-find prob lem in [2].