title: Big O of union method of dynamic connectivity problem
body: <p>i faced a paradox to analyse this function, Why the time complexity of this function is N^2 and not N?</p>
  <pre class="lang-java prettyprint-override"><code>public void union(int a, int b) {
          int aid = ids[a];
          int bid = ids[b];
          for (int i = 0; i &lt; ids.length; i++) {
              if (ids[i] == aid) {
                  ids[i] = bid;
              }
          }
      }
  </code></pre>
  <p>Its an implementation of eager approach, to solve dynamic connectivity problem , complete code is:</p>
  <pre class="lang-java prettyprint-override"><code>// Union method has N^2 time complexity!!
  class EagerApproach extends UnionFind {
  
  
      protected int[] ids;
  
      EagerApproach(int[] input) {
          super(input);
          ids = new int[input.length];
          System.arraycopy(input, 0, ids, 0, input.length);
      }
  
  
      public boolean connected(int a, int b) {
          return ids[a] == ids[b];
      }
  
      public void union(int a, int b) {
          int aid = ids[a];
          int bid = ids[b];
          for (int i = 0; i &lt; ids.length; i++) {
              if (ids[i] == aid) {
                  ids[i] = bid;
              }
          }
      }
  
      public int[] getIds() {
          return ids;
      }
  }
  </code></pre>