Why I can't calculate time complexity by multiplying?

Question

I want to get the time complexity of this pseudocode:

count = 0;
for (i = 1; i < n; i *= 2) 
    for (j = 0; j < i; j++) 
        count++;

I thought it was log(n)*log(n), but the answer is log(n). I was told that because i*2 has nonlinear growth, I can't multiply directly.

I am confused why I can't do that: I don't know the rules about when I can multiply when I can't. When I calculate time complexity, I just multiply them when I meet nested loops. How should I calculate it correctly?

Answer 1

The answer you got is wrong. The complexity is O(𝑛).

For a given 𝑖, the number of iterations of the inner loop is equal to 𝑖, and 𝑖 will take the value of each power of 2 that is less than 𝑛. There are ⌈log₂𝑛⌉ such powers. And so the total number of iterations of the inner loop is the sum of those powers, i.e.

2⁰ + 2¹ + 2² + ... + 2^{⌈log₂𝑛⌉−1}

This is the sum of the first terms of a Geometric series, and thus equal to:

2^{⌈log₂𝑛⌉}−1

This is O(𝑛).

We can illustrate this by running the script for several values of 𝑛, notably powers of 2:

function getCount(n) {
    let count = 0;
    for (let i = 1; i < n; i *= 2) 
        for (j = 0; j < i; j++) 
            count++;
    return count;
}

for (let n = 1; n < 70000; n *= 2) {
    let count = getCount(n);
    console.log("For", n, "count is", count);
}

As you can see the number of times that count++ executes is one less than the value of n, when n is a power of 2.