What is the complexity of path compression technique for disjoint set algorithm?

Question

I was studying the disjoint algorithm with the union by rank and path compression.

It is clear to me if Union by rank is used then the find() operation complexity is O(log(n)).

But I wonder what is the complexity of the path compression technique for disjoint set algorithm if I use union by rank or not use union by rank?

Answer 1

If you link the sets together arbitrarily instead of using union-by-rank or union-by-size, then path compression alone will achieve O(m log n) time for any sequence of n unions and m finds (with m > n). That makes the amortized cost of a find operation O(log n)

The proof is difficult, so here's an excellent confirmatory reference: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf