Simpler Analyses of Union-Find

Zhiyi Huang, Chris Lambert, Zipei Nie +1

We analyze union-find using potential functions motivated by continuous algorithms, and give alternate proofs of the $O(\log \log n)$, $O({\log }^{\ast }n)$, $O({\log }^{\ast \ast }n)$, and $O(α(n))…