Linuxn00b - 4 months ago 10
Java Question

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

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!

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`