Disjoint-set (aka union–find or merge-find). Because good implementations can merge and find in log* (iterated logarithm) amortized time.
-
Inverse Ackermann, even! That's better than log*! Ostensibly. In this universe, the difference is slight, I'll admit.
Very Interesting. I see that on Wikipedia now. Do you have a link to a proof for O(α(n))? I only know the proof for O(log* n).
-
-
A talk trying to explain it somewhat more clearly is http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf …
-
(the original paper by Tarjan refers to another earlier paper by Tarjan for the proof, and notes at the same time that proof had a mistake.)
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.