Time complexity for dependant nested for loop?

Question

Can you explain me how to find time complexity for this?

sum=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=k;j++)
     sum++;

So, i know the outer loop has time complexity of O(logn), but since the iterations of the inner loop depends on the value of the outer loop, the complexity of this algorithm is not O(nlogn).

The book says it is O(n).

I really dont understand how it is O(n)...Can someone please explain it... I'll be really grateful if u could go into the details btw :D

A mathematical solution would help me understand better...

Answer 1

The outer loop executed log(Base2)n times.so it is O(log(Base2)n).

the inner loop executed k times for each iteration of the outer loop.now in each iteration of the outer loop, k gets incremented to k*2.

so total number of inner loop iterations=1+2+4+8+...+2^(log(Base2)n)
=2^0+2^1+2^2+...+2^log(Base2)n (geometric series)
=2^((log(base2)n+1)-1/(2-1)
=2n-1.
=O(n)
so the inner loop is O(n). So total time complexity=O(n), as O(n+log(base2)n)=O(n).

UPDATE:It is also O(nlogn) because nlogn>>n for large value of n , but it is not asymptotically tight. you can say it is o(nlogn)[Small o] .