title: Why is the time complexity O(lgN) for an operation in weighted union find algorithm?
body: <p>So everywhere I see weighted union find algorithm, they use this approach:</p>
  
  <ol>
  <li>Maintain an array pointing to the parent node of a particular node</li>
  <li>Maintain an array denoting the size of the tree a node is in</li>
  <li>For union (p,q) merge the smaller tree with larger</li>
  </ol>
  
  <p>Time complexity here is O(lgN)</p>
  
  <hr>
  
  <p>Now an optimzation on this is to flatten the trees, ie, whenever I am calculating the root of a particular node, set all nodes in that path to point to that root.</p>
  
  <p>Time complexity of this is O(lg*N)</p>
  
  <hr>
  
  <p>This I can understand, but what I don't get is why don't they start off with an array/hashset wherein nodes point to the root (instead of the immediate parent node)? That would bring the time complexity down to O(1).</p>