Deriving time complexity of Union-Find using only path compression

73 Views Asked by At

For the Union-Find algorithm, I've read that using path compression alone gives a worst-case running time of $O(n+f\cdot(1+\log_{2+\frac{f}{n}}(n)))$ for a sequence of $n$ MakeSet operations (and hence at most $n-1$ Union operations) and $f$ Find operations. So far, I've only ever seen it stated without proof (e.g., here). Can someone explain how to derive this time complexity?