Confuse with log(n) behaviour

Question

s=0; 
for(i=1;i<n;i=i*2) 
{ 
    for(j=0;j<n;j++)
    {
        s=s+i*j;
    } 
    s=s+1;
}

I'm trying to establish the big-o complexity for the above algorithm. The outer loop starts at 1 and runs to n, counter in i doubles for each iteration, thus this is a log(n) behaviour. The inner loop runs from 0 to n with O(n) behaviour. I'm confused whether it is O(n * log(n)) or not, the order matters or not? Also j starts at 0, not at 1 so this can't be O(n * log(n))?

Answer 1

In this case, the inner loop is independent of the outer loop. So we can just count the number of times outer loop runs and then multiply it with the number of times inner loop runs and that will be the complexity.

No. of times outer loop runs is log2(n) as the number is being multiplied by 2 each time.

No. of times inner loop runs is always n.

Thus, complexity will be O(nlog2(n)).

Answer 2

You can actually count how many times the inner loop runs in a simple case like this. It will give a good indication of the asymptotic behavior as n changes. Here's a quick javascript example:

function count(n) {
    let count=0; 
    for(i=1; i<n; i=i*2) 
    { 
        for(j=0;j<n;j++)
        {
            count++
        } 
       
    }    
    return count
}
let n = 1024
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 32768
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 1048576
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

The behavior looks like O(nlog(n)) to me. Additionally it stands to reason that performing log(n) loops that each perform n iterations will be O(nlog(n)) because n * log(n) === log(n) * n