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?