question about runtime of taking union in Kruskal's algorithm

[w***@hotmail.com]

Could someone explain why union takes order O(nlogn) in the Kruskal's
algorithm?

[Kwok-Chiang Andrew Chung]

Post by w***@hotmail.com
Could someone explain why union takes order O(nlogn) in the Kruskal's
algorithm?

Okay, so the suggest implementation of union-find given in lecture is an
array C[1..n], where n is the number of vertices.

C[i] = The component # that vertex i is in.

So let's suppose we have 4 components in the current stage of Kruskal's.

i 1 2 3 4 5 6 ... n
C[i] 1 4 2 3 1 2 ... 1

The union operation joins 2 components together, so if we want to union
component 1 and component 2, we want to rename all the vertices in
component 1 to component 2, or vice versa.

You could do a linear scan of the C array and rename vertices as you going
along, and that's in n^2 time.

I just asked Professor Lubiw for more clarification about the n * log(n)
time earlier. Basically you need to keep track of the sizes of each
component and have the larger set absorb the smaller set. So for a
particular element, it gets absorbed from a set of size i into a set of
size 2 * i. So the number of absorbs is bounded by log(n), since a set of
size 1 can only double in size log(n) times. Using this logic for n
elements, we have union-find in O(n * log n) time.

She said that the O(n log n) approach is a bit more advanced than we need
to know for the exam.

I assume (she didn't say this) that n^2 union-find is fair game.

[Anna Lubiw]

Just to confirm, I did not give the details in class, and you
are not responsible for them for the midterm.

Anna Lubiw

Post by Kwok-Chiang Andrew Chung

Post by w***@hotmail.com
Could someone explain why union takes order O(nlogn) in the Kruskal's
algorithm?

Okay, so the suggest implementation of union-find given in lecture is an
array C[1..n], where n is the number of vertices.
C[i] = The component # that vertex i is in.
So let's suppose we have 4 components in the current stage of Kruskal's.
i 1 2 3 4 5 6 ... n
C[i] 1 4 2 3 1 2 ... 1
The union operation joins 2 components together, so if we want to union
component 1 and component 2, we want to rename all the vertices in
component 1 to component 2, or vice versa.
You could do a linear scan of the C array and rename vertices as you going
along, and that's in n^2 time.
I just asked Professor Lubiw for more clarification about the n * log(n)
time earlier. Basically you need to keep track of the sizes of each
component and have the larger set absorb the smaller set. So for a
particular element, it gets absorbed from a set of size i into a set of
size 2 * i. So the number of absorbs is bounded by log(n), since a set of
size 1 can only double in size log(n) times. Using this logic for n
elements, we have union-find in O(n * log n) time.
She said that the O(n log n) approach is a bit more advanced than we need
to know for the exam.
I assume (she didn't say this) that n^2 union-find is fair game.