Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question
    
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 by (I think) Dexter Kozen, which contain a proof. –  Rahul Jul 20 '12 at 3:24
    
@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)$ –  user26649 Jul 20 '12 at 3:42

1 Answer 1

I don't think that "...approximately yields amortized complexity $O(1)$" is a good statement. There is a very clear notation what approximation means when speaking about algorithms. It is better to phrase it as "... in the amortized running time per operation is effectively a small constant." as done in Wikipedia. This means that for all practical values the inverse Ackermann finction $\alpha(n)$ can be bounded by a constant, since it grows very slow.

If you want to get an idea, why the $\alpha(n)$ shows up, I recommend the very readable article by Seidel and Sharir. The paper shows first a $O(\log n)$ bound and then improves the bound to $O(\log^* n)$. However, the idea behind the improvement is still applicable to the $O(\log^* n)$ bound, and gives an even better bound. The repeated improvements culminate in the bound of $\alpha(n)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.