What is the worst-case running time of unions done by size and path compression?

Category: QuestionsWhat is the worst-case running time of unions done by size and path compression?
Editor">Editor Staff asked 4 weeks ago

What is the worst-case running time of unions done by size and path compression?
 
(a) O(N)
 
(b) O(logN)
 
(c) O(N logN)
 
(d) O(M logN)
 
My question is based upon Trees topic in section Trees of Data Structures & Algorithms I
 
The question was asked by my school teacher while I was bunking the class.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (d) O(M logN)
 
For explanation: The worst case running time of a union operation done by size and path compression is mathematically found to be  O(M logN).