Worst-case and amortised optimality in union-find (extended abstract)
Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe · 1999
We study the interplay between worst-case and amortised time bounds for the classic Disjoint Set Union problem (Union-Find). We ask whether it is possible to achieve optimal worst-case and amortised bounds simultaneously. Furthermore we would like to allow a tradeoff between the worst-case time for a query and for an update. We answer this question by first providing lower bounds for the possible worst-case time tradeoffs, as well as lower bounds which show where in this tradeoff range optimal amortised time is achievable. We then give an algorithm which tightly matches both lower bounds simultaneously. The lower bounds are provided in the cell-probe model as well as in the algebraic real-number RAM, and the upper bounds hold for a RAM with logarithmic word size and a modest instruction set. Our lower bounds show that for worst-case query and update time tq and tu respectively, one must have tq = \\Omega (log n = log tu), and only for tq * ff(m; n) can this tradeoff be achieved simultaneously with the optimal amortised time of \\Theta (ff(m; n)). Our