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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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 function $\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|cite|improve this answer

Your Answer

 
discard

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