Weighted Union Find

Question

Prove that the weighted union (w_union) takes O(log2(n)) for FIND in the worst case on a graph which has n nodes by proving by induction.

I'm not sure how I would prove this at all, I know how I would prove recurrences but this has stumped me and I'm not sure how I would do this or even get started at all.

If someone can help me out with this, that would be great.

Thanks guys.

code:

public void w_union(int u, int v) { int pu, pv, nu, nv;

   pu= c_find(u);
   pv= c_find(v);

   if (pu == pv) return;

   nu= -1 * parent[pu]; /* nu = # nodes in component with u. */
   nv= -1 * parent[pv]; /* nv = # nodes in component with v. */

   if (nu <  nv)
   { /* pv is the new root. */
      parent[pv]+= parent[pu]; /* Update # nodes. */
      parent[pu]= pv;
   }
   else
   { /* pu is the new root. */
      parent[pu]+= parent[pv]; /* Update # nodes. */
      parent[pv]= pu;
   }

}

    int c_find(int u)
   {   int v, top;
        top=0;
        while (parent[u] >= 0)
        {
           stack[top]= u; top++;
           u=parent[u];
        }
        while (top > 0)
        {
            top--; v= stack[top]; 
            parent[v]=u;
        }
        return(u);
   }

Answer 1

FIND just goes up and down the tree, so the complexity of FIND is $O(\textrm{maximum possible tree height for }n\textrm{ nodes})$. Therefore all you have to show is that a weighted-union-find tree with $n$ nodes has height $O(\log_2 n)$.

Let $H(n)$ be the height of the tallest possible w-u-f tree with $n$ nodes. Clearly $H(1)=0$.

Any w-u-f tree of $n>1$ nodes resulted from merging a w-u-f tree with $n_1$ nodes and one with $n_2\le n_1$ nodes. The resulting tree of $n=n_1+n_2$ nodes has height at most $\min(H(n_1),H(n_2)+1)$, because when merging, weighted union-find always puts a tree with fewer nodes below the root of the other tree. Then, because $n_2\le\frac{n}{2}$, we see that $H(n)\le H(\frac{n}{2})+1$, and therefore $H(n)\le \log_2 n =O(\log_2 n)$ as needed.