0
$\begingroup$

For optimization of Find operations (an operation that returns the representative of the set a node belongs to) in a disjoint-set structure, path compression is used. Analysis of the operation approximately yields amortized complexity $\mathcal{O}\left(1\right)$.

Wikipedia and a variety of other sources provide brief explanations - most identify the relation between path compression and the inverse Ackermann function, however do not provide a compendious description of the reasoning behind the relation.

Why is the approximated amortized complexity of path compression in Find operations $\mathcal{O}\left(1\right)$?

  • 0
    What does "*approximated* amortized complexity" mean? The amortized complexity of union-find with path compression is $O(\alpha(n))$, where $\alpha(n)$ is the inverse of the Ackermann function, and this is not $O(1)$. In any case, searching for "union find ackermann" on Google turns up a number of results, for example [these course notes](http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/48-57.pdf) by (I think) Dexter Kozen, which contain a proof.2012-07-20
  • 0
    @RahulNarain The inverse Ackermann function is an *extremely* slow growing function. For $n$ less than $2^{65536}$ (in other words all practical situations), $\mathcal{O}(\alpha(n))$ is equal to or less than $6$. Therefore for all realistic situations, $\mathcal{O}(\alpha(n))$ is *approximately* $\mathcal{O}(1)$2012-07-20

1 Answers 1