Simpler Analyses of Union-Find
share
We analyze union-find using potential functions motivated by continuous algorithms, and give alternate proofs of the O(loglogn), O(log^*n), O(log^**n), and O(α(n)) amortized cost upper bounds. The proof of the O(loglogn) amortized bound goes as follows. Let each node's potential be the square root of its size, i.e., the size of the subtree rooted from it. The overall potential increase is O(n) because the node sizes increase geometrically along any tree path. When compressing a path, each node on the path satisfies that either its potential decreases by Ω(1), or its child's size along the path is less than the square root of its size: this can happen at most O(loglogn) times along any tree path.
READ FULL TEXT