What would a worst-case input for quick-union look like?

LalSalaamComrade@lemmy.ml to General Programming Discussion@lemmy.ml – 12 points –

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?

0

No comments yet. You could be first!