From Sedgewick’s book Algorithms in C:
Property 1.2
For M > N, the quick-union algorithm could take more than MN/2 instructions to solve a connectivity problem with M pairs of N objects.
I am not really able to follow up this. From what I understand, if M (number of union operations) exceed the count of N objects, it could lead to a performance penalty.
What would the inputs look like for the worst-case scenario? From the book, it says that of all the M pairs, the first N-1 pair will be connected in the consecutive pattern 0-1, 1-2, 2-3, and from what I understand, it creates a tall tree. But, is that all? What about the remaining pairs?
You must log in or register to comment.