0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.