Time Complexity of Dependent Nested Loop

Question

Hi I've been trying to understand what the time complexity of this nested loop will be for a while now.

int i = 1;
while(i < n) {
    int j = 0;
    while(j < n/i){
        j++;
    }
    i = 2 * i;
}

Based on the couple of calculations I've done I think its Big O notation is O(log(n)), but I'm not sure if that is correct. I've tried looking for some examples where the inner loop speeds up at this rate, but I couldn't find anything.

Thanks

Fernando Aires · Accepted Answer · 2014-09-19 07:41:28Z

1

One information that surprisingly few people use when calculating complexity is: the sum of terms is equal to the average multiplied by the quantity of terms. In other words, you can replace a changing term by its average, and get the same result.

So, your outer while loop repeats O(log n) times. But the inner while loop, repeats: n, n/2, n/4, n/8, ..., 1, depending on which step of the outer while are we. But (n, n/2, n/4, ..., 1) is a geometric progression, with log(n) terms, and ratio 1/2, which sum is n.(1-1/n)/(1/2) = 2n-2 \in O(n). Its average, therefore, is O(n/log(n)). Since it repeats O(log(n)) times, the whole complexity is O(log(n)*n/log(n)) = O(n)...

answered Sep 19, 2014 at 7:41

Fernando Aires

5312 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

doaderek Over a year ago

Thanks, I see where I messed up in my summation.

Collectives™ on Stack Overflow

Time Complexity of Dependent Nested Loop

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related