Complexity for nested loops dividing by 2

问题:

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. The code is as follows:

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

I have arrived that the first loop is of O(log_2(n)). As for the second loop I am a little lost! Thank you for the help in the analysis.

回答1:

To formally solve the your algorithm's time complexity, you may use the following steps with Sigma notation:

Also, take a look a the last slide of this very interesting document by Dr. Jauhar.

回答2:

The overall number of iterations of inner loop is n + n/2 + n/4 + ... + 1 which is approximately 2n. So the complexity is O(n).

回答3:

Complexity should be O(n). It forms a geometric series (not exactly but approximately).

The loop runs for n+ n/2 + n/4 + .... +1 which is approx 2n.

And O(2n) = O(n).