Time Complexity

#1

int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;

What can be the time complexity here ?

#2

Series becomes n + n / 2 + n / 4 + n / 8 + … . This convergent series can be summed up easily as :- n ( 1+ 1/2 + 1/4 + …) . This is an infinite GP with sum 2. Thus complexity is O(n).

#3

What about the inner loop ?

#4

Yes, for the inner loop only I counted the individual terms in the series. The outer loop just helps in determining the no. of iterations of inner loop.