Complexity of given program.

Question

Consider the following C segment:

main()
{
    int sum = 0; 
    for(int b=1; b<=n; b*=2)
    {
        for(int i=0; i<b; i++)
        { 
            for(int j=0; j<n; j+=2)
            { 
                sum += j; 
                
            } 
            for(int j=1; j<n; j*=2)
            {
                sum *= j; 
            }
        } 
        
    } 
    
}

The complexity of above program is ____________.

Comments

i is running total of O(n) times

 @joshi_nitish Can you please explain this.

---

I'm confused now. A detailed explanation is much needed.

---

I think I got it. Please check if I am right or not

The outermost loop will run 'log n' times. Now for the loop:

for(i=0;i<b;i++) 

It will run for 1+2+4+8+...+n which is approx. equal to $2^{n}$ and here 'n' equals log n, therefore, it becomes $2^{log n}$ which is equal to 'n' only. And the loop

for(int j=0; j<n; j+=2) 

has complexity (n/2) ~ O(n) and hence complexity

O(n) * O(n) = O($n^{2}$)