<p>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.</p>

CC BY-SA 3.0
2015-12-04T23:13:37.043Z
2015-12-04T23:13:37.043Z
David Eppstein
<p>In 1979, Robert Tarjan published <a href="http://www.sciencedirect.com/science/article/pii/0022000079900424">"A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets"</a>, 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.</p>

<p>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?</p>

<ds.data-structures>
Improved lower bounds or upper bounds on union-find structures since Tarjan?
templatetypedef
# Improved lower bounds or upper bounds on union-find structures since Tarjan?

(Asked by: username_0 on 2015-12-04)

In 1979, Robert Tarjan published ["A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets"](http://www.sciencedirect.com/science/article/pii/0022000079900424), 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?

**Tags:** ds.data-structures

---

## 1 answers

### Answer by username_1 on 2015-12-04. Score: 13 | Accepted answer

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.


---

