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] .

Answer 2

Just see how many times the inner loop runs:

1 + 2 + 4 + 8 + 16 +...+ n

Note that if n = 32, then this sum = 31 + 32. ~ 2n.
This is because the sum of all the terms except the last term is almost equal to the last term.

Hence the overall complexity = O(n).

EDIT:

The geometric series sum (http://www.mathsisfun.com/algebra/sequences-sums-geometric.html) is of the order of:

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

Answer 3

I believe you should proceed like the following to formally obtain your algorithm's order of growth complexity, using Mathematics (Sigma Notation):