6
$\begingroup$

In 1979, Robert Tarjan published "A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets", which proved an upper bound of $O(m \alpha(n))$ time on the time complexity of performing $m$ operations on a disjoint-set forest with union-by-rank and path compression, assuming there are $n$ nodes. He also proved a matching lower bound on any data structure for this problem in a pointer machine.

Since this paper was published, has anyone devised an data structure that runs in $o(m \alpha(n))$ for this problem? (Such a data structure would have to rely on techniques that don't work on a pointer machine.) Or are there any new lower bounds on non-pointer-machines?

$\endgroup$
13
$\begingroup$

There's a matching lower bound in the cell probe model (with a logarithmic number of bits per memory cell); see Fredman and Saks, "The cell probe complexity of dynamic data structures", STOC 1989.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.