Time Complexity

Question

What is the time complexity of this?

for(i=1;i<=n;i=i*2)

   {

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

          {temp=temp+i;}

}

Answer 1

See for 

i = 1 , j runs 1 time 

i = 2 , j runs 2 times

i = 4 , j runs 4 times

..

So like this we will have logn terms till we reach i = n as i is doubled everytime..

So 

T(n)  =  1 + 2 + 4 ...............logn terms

        =  1(2^logn - 1) / (2-1)

        =   O(n)

Hence the time compexity of above code is O(n)..