If we use trees with the union-by-rank algorithm, what is the worst case running time for checking if two elements are in same set or not?
How come it’s answer is O(N^2)?
Isn’t worst case complexity of this algo is O(logn)?
Q1. Union By Rank
@dhruvgupta1498
As loop in Union function iterates through all the N elements for connecting two elements. So performing this operation on N objects will take O(N2) time, which is quite inefficient.
dont forget to hit like and mark resolved if cleared otherwise ask 
@vatsal38
In union function we just make a call to get super parent which works in O(logn). So if we make to all vertices then also it should be O(nlogn). How is it O(n^2)?
@dhruvgupta1498 yes using union by rank worst case reduces to o(logn). i have asked the team whether the ans is given correct or not. will tell you when they reply
correct ans is logn its updated
1 Like