title: Time Complexity of Array based Disjoint-Set data structure
body: <p>I was solving <a href="https://www.codechef.com/problems/DISHOWN" rel="nofollow">this</a> question on CodeChef and going through the <a href="https://discuss.codechef.com/questions/47241/dishown-editorial" rel="nofollow">editorial</a>.</p>
  
  <p>Here's the pseudo-code for the implemented disjoint-set algorithm : </p>
  
  <pre><code>Initialize parent[i] = i  
  Let S[i] denote the initial array.
  
  int find(int i)
      int j
      if(parent[i]==i)
                  return i
      else
          j=find(parent[i])
          //Path Compression Heuristics
          parent[i]=j
          return j
  
  set_union(int i,int j)
      int x1,y1
      x1=find(i)
      y1=find(j)
      //parent of both of them will be the one with the highest score
      if(S[x1]&gt;S[y1])
          parent[y1]=x1
      else if ( S[x1] &lt; S[y1])
          parent[x1]=y1
  
  solve()
      if(query == 0)
          Input x and y
          px = find(x)
          py = find(y)
          if(px == py)
              print "Invalid query!"
          else
              set_union(px,py)
      else
          Input x.
          print find(x)
  </code></pre>
  
  <p>What is the time complexity of <code>union</code> and <code>find</code> ?</p>
  
  <p>IMO, the time complexity of <code>find</code> is <code>O(depth)</code>, so in worst case, if I am not using path-comression, the complexity turns out to be O(n). Since <code>union</code> also uses <code>find</code>, it also has the complexity of O(n). If instead we throw out the <code>find</code> from <code>union</code> and instead pass the parents of two sets to <code>union</code>, complexity of <code>union</code> is O(1). Please correct me, if I am wrong.</p>
  
  <p>If path compression is applied, then what is the time complexity?</p>