I am learning weighted quick union algorithm by princeton university. I am stuck on mathematical proof of how this algorithm has time complexity of O(lgN)? I know how it is better than normal quick union merging smaller trees below larger tress but how did they come out with the time complexity lgN is something which I couldn't understand. It would be helpful if you can help me understand this. This is the code I am working on:

public class WeightedQuickUnionUF {

    private int[] id;
    private int[] sz; //an extra array `enter code here`to count the number of objects in the tree rooted at i.

    public WeightedQuickUnionUF(int N){
        sz = new int[N];


        id = new int[N];
        for(int i = 0 ; i<N ; i  ){
            id[i] = i;
            sz[i] = 1;
        }
    }

    public int root(int i){
        while(id[i] != i)
            i = id[i];

        return i;
    }//will keep searching until the index and the value at the index are equal

    public boolean connected(int p , int q){
        return root(p) == root(q);
    }//identical to quick union

    public void union(int p , int q){
        int i = root(p);
        int j = root(q);

        if(i == j )
            return;
        if(sz[i] < sz[j]){
            id[i] = j;
            sz[j]  = sz[i];
        }
        else{
           id[j]= i;
           sz[i]  = sz[j];
        }

        System.out.println(p   " and "   q   " are now connected.");

    }/*Link smaller tree to root of larger tree
    and update the sz[]array */


    public void print(){
        System.out.println("0 1 2 3 4 5 6 7 8 9");
        System.out.println("-------------------");
        for (int j : id) {
            System.out.print(j   " ");
        }
    }

}

CodePudding user response：

If you attach the smaller tree to the root of the larger, the total height only increases (by one) if the two heights are the same.

So a strategy to obtain a tree as high as possible with as few nodes as possible (which corresponds to the worst case) is by making trees of equal height only and uniting them.

The picture below shows trees of heights from 1 to 4 with the minimum number of nodes. It is obvious that they include n=2^(h-1) nodes.

It is important to realize that using the "weighted" rule, it is impossible to build higher trees with the same number of nodes, hence h=1 lg(n) is the worst case. (And of course, the running time for a find is proportional to the tree height in the worst case.)