Linuxn00b - 8 months ago 29

Java 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

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`