Question

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.

Answer 1

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).