Why union-find algorithm runs in amortized time?

Question

I have an exercise that is stated:

What's amortized time of series on $n$ operations where all union operations precede find operations?

I know it should be $n$ for series but I struggle with proving that.

Maybe someone fluent with proofs could help me?

Answer 1

A bungling proof

A series of $n$ union operations (or find ones) on $m$ elements run in $O(n\;\alpha(m))$, where $\alpha$ is the inverse Ackermann function.

To get a sense of its growth, observe that

$$\alpha(m) = \begin{cases} 0, & 0\le m \le 2,\\ 1, & m = 3,\\ 2, & 4 \le m \le 7\\ 3, & 8 \le m \le 2047\\ 4, & 2048 \le m \le 16^{512} \gg 10^{80}\\ 5, & 16^{512} \le m \le \dots \end{cases}$$

You can see that Inverse Ackermann function verifies $0 \leq \alpha(m) \leq 4$ for all practise inputs of size $m$ (note that $10^{80}$ is the estimated number of atoms of the universe), so it is considered that $$\alpha(m) \subset O(1)$$ This results implies that a series of $n$ union operations on $m$ elements run in $O(n)$ time in an average case.

A complete proof

Wait until someone smarter than me posts ;). Alternatively, you've got a complete proof in

Thomas H. CORMEN; Charles E. LEISERSON; Ronald L. RIVEST; Clifford STEIN (2009). Introduction to Algorithms. Third Edition.

See Chapter 21 - Data Structures for Disjoint Sets, Section 21.4 - Analysis of union by rank with path compression (pages 573-582).