title: Determining Time Complexity of Merge K Sorted Arrays
body: <p>I wrote a Merge K Sorted Arrays. I found the best time Time Complexity for this to be O(n<em>k Logk) on other sites, where <code>k</code> is the number of Arrays and <code>n</code> is the number of elements in each array. 
  I think mine is O(n</em>k).</p>
  
  <p>Can anybody confirm this?? The code is below.</p>
  
  <pre><code>private static void MergeKSortedArrays()
  {
      int[][] arr = { new int[] { 3, 5, 7 }, new int[] { 1, 2, 4 }, new int[] { 6, 8, 9 } };
      int k = 3, n = 3;
  
      int[] output = new int[n * k];
      int[] temp = new int[k];
  
      for (int i = 0; i &lt; k - 1; i++)
      {
          temp = Merge(arr[i], arr[i + 1]);  // takes Linear time
          arr[i + 1] = temp;
      }
  
      foreach(int i in arr[k-1])
      {
          Console.Write(i + " ");
      }
      Console.WriteLine();
  
  }
  
  private static int[] Merge(int[] a, int[] b)
  {
      int[] o = new int[a.Length + b.Length];
      int i = 0, j = 0, ind = 0;
  
      for (; i &lt; a.Length &amp;&amp; j &lt; b.Length;)
      {
          if (a[i] &lt;= b[j])
          {
              o[ind] = a[i];
              i++;
              ind++;
          }
          else
          {
              o[ind] = b[j];
              j++;
              ind++;
          }
      }
  
      if (i &lt; a.Length)
      {
          for (; i &lt; a.Length; i++, ind++)
          {
              o[ind] = a[i];
          }
      }
      else if (j &lt; b.Length)
      {
          for (; j &lt; b.Length; j++, ind++)
          {
              o[ind] = b[j];
          }
      }
  
      return o;
  }
  </code></pre>