Weighted Union

Lemma: With W-UNION, any tree that has k nodes has depth at most .

Let ,
d = , if
= , if

BASIS:

HYPOTHESIS: for , depth

INDUCTION:

I)

II)

Lemma: A UNION-FIND PROGRAM of size n does link operations in the worst case if the weighted union is used.