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
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)...
