Why does Union-Find have time complexity O(N + M lg* N) with the "log star N"?

Question

The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be

$$ O(N + M \lg^*N) $$

and the $ lg^*N $ is "log star N" and is iterated logarithm. It can be almost taken to be a constant, as $ lg^*2^{65536} $ is only equal to 5. Why is it $ lg^*N $ and what kind of operations / algorithm typical can produce $ lg^*N $?

Answer 1

Check out the analysis of path compression in Union-Find by Seidel and Sharir "Top-Down Analysis of Path Compression", SIAM Journal of Computing 34:3 (2005), pp 515-525. Somewhat heavy going, the result you cite is a step on the way to the best-possible bound by their method.