title: Weighted quick-union with path compression algorithm: time complexity analysis
body: <p>I'm learning "Weighted quick-union with path compression" algorithm for an union/find structure. The <a href="https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf" rel="nofollow">Princeton edu site</a> explained detailedly the algorithm.
  And here is the implementation in Java:</p>
  
  <pre class="lang-java prettyprint-override"><code>public class WQUPC {
    private int[] id;
    private int[] sz;
    public WQUPC(int N) {
      id = new int[N];
      sz = new int[N];
      for (int i = 0; i &lt; N; i++) {
        id[i] = i;
        sz[i] = 1;
      }
    }
  
    int root(int i) {
      while (i != id[i]) {
        id[i] = id[id[i]];
        i = id[i];
      }
      return i;
    }
  
    boolean connected(int p, int q) { return root(p) == root(q); }
  
    void union(int p, int q) {
      int i = root(p);
      int j = root(q);
      if (sz[i] &lt; sz[j]) {
        id[i] = j;
        sz[j] += sz[i];
      } else {
        id[j] = i;
        sz[i] += sz[j];
      }
    }
  }
  </code></pre>
  
  <p>But just like the website mentions about its performance:</p>
  
  <blockquote>
    <p>Theorem: Starting from an empty data structure, any sequence
    of M union and find operations on N objects takes O(N + M lg* N) time.</p>
    
    <p>• Proof is very difficult.</p>
    
    <p>• But the algorithm is still simple!</p>
  </blockquote>
  
  <p>But I'm still curious about how comes the iterative logarithm lg*n. How is it derived? Can someone prove it or just explain it in an intuitive way?</p>