1

I need help figuring out why the following code-snippet in Java is O(nlogn) instead of O(n^2). Any help please?

int sumSome(int[] arr){
   int sum = 0;
   for (int i=0; i<arr.length;  i++) {
      for (int j=1; j<arr.length; j = j*2) {
         if (arr[i] > arr[j])
            sum += arr[i];
      }
   }
   return sum;
}
jdaz
  • 5,964
  • 2
  • 22
  • 34
Lv25_Magikarp
  • 11
  • 1
  • 2
    It is because `j` doubles in each iteration of the inner loop (`j = j*2`). If it only increased by 1 each time, then the code would be O(n^2) – jdaz Jul 23 '20 at 19:51
  • Oh I thought It was because of the j*2 initially as well. But could you explain in more detail what that does to every iteration of the inner loop to cause the entire code-snippet to be dominated by O(nlogn)? – Lv25_Magikarp Jul 23 '20 at 20:04
  • 2
    In the inner loop we are iterating on power of 2 like j = 1, 2, 4, 8.... it will stop at some iteration k such that 2^(k +1) > n. so we will do O(logn) iterations in the internal loop. And the outer loop will always be n. So overall it is O(nlogn) – Deepak Patankar Jul 23 '20 at 20:13

1 Answers1

5

It may be helpful to think of a general number interval, say 1 to 100.

  • If you loop through that interval one by one, the loop will be O(n)
  • If you loop through it by any linear step size, like 2 at a time or 10 at a time, the loop will be O(n/2), O(n/10), etc., which still simplifies to O(n).

However, if the size of the loop step changes each time through the loop, you get different results:

  • If you loop through the range while doubling the step each time (1, 2, 4, 8, 16, 32, 64), you will end up running the loop only 7 times before reaching the end. This is exponential growth of the step size, which corresponds to a logarithmic number of times through the loop: 1 + log(100) with log base 2 (rounded down), which simplifies to O(log n).
  • If you multiply your step size by 3 each time (1, 3, 9, 27, 81), it will loop 1 + log(100) times with log base 3, which still simplifies to O(log n). And so on.

So in your example, you have your outer loop O(n) times your inner loop O(log n), leading to a combined O(n * log n).

Great examples of different time complexities can be found in this answer.

jdaz
  • 5,964
  • 2
  • 22
  • 34
  • 1
    Oh wow this makes so much more sense now! I greatly appreciate your helping solving the Big-O classification of this nested loop. This was so helpful and clearly explained! I can't thank you enough. – Lv25_Magikarp Jul 23 '20 at 22:24