CODEWITHSUNDEEP
algorithmdisjoint-setsunion-find
Muidul Alam 2hin
Muidul Alam 2hin

Reputation: 189

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

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?

Upvotes: 3

Views: 6678

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59194

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

Upvotes: 8

Related Questions