How to measure the time-complexity (Big-O) of this algorithm?

Question

I'm attempting to measure the big-O complexity of the following algorithm:

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;
}

Now from my understanding,

if (arr[i] > arr[j])
                sum += arr[i];

has big O of O(1) since it's constant and nothing is happening however, the for loop that sounds it though I'm having a hard time attempting to discern its Big-O notation. I assumed that

for (int j=1; j<arr.length; j = j*2) {
         if (arr[i] > arr[j])
            sum += arr[i];
}

is a linear function O(n) because j maybe 1 but it's going up in a linear fashion at O(2n) which is just O(n). So wouldn't the entire algorithm be O(n^2)? Apparently I didn't answer the question correctly on a MOOC exam. Thanks!

Answer 1

The key to Big-O is looking for loops, so your key piece is here:

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];
   }
}

The outer loop executes N times, since it goes from 0 to N in increments of 1.

The inner loop executes Log N times, per outer iteration, because it does from 1 to N exponentially. (The piece you missed, I suspect, is the iterator in the loop: j = j*2. This makes J increase exponentially, not linearly, so it'll reach N in log-base-2 time. It would be linear if it was +2, instead of *2)

The if inside doesn't matter for Big-O, as it only adds a coefficient.

So, just multiply the orders of the loops: N * Log N = N Log N