time complexity of the given loop

Question

Please tell me the time complexity of fun():-

    int fun(int n)
    {
         int count = 0;
        for (int i = n; i > 0; i /= 2)
              for (int j = 0; j < i; j++)
                    count += 1;
              return count;
    }

According to me, it is the summation of n+(n/2)+(n/4)+....+1 so it comes out to be (2^n) - 1. Then what's the time complexity?? In the answer its given O(n). Is it correct ??
    Please tell if I am missing some concept.

Answer 1

Let say N  is power of 2 ,  

For example let say N  = 16 ,

Now according to code ,  

it runs 16 + 8 + 4 + 2 + 1  

Its a Geometric Progression ,  formula for sum of GP is  ( a * ( r^n - 1  ) / ( r - 1 ) )

a = first  term , r = common ratio.

Here a = 1  and r = 2 ,

Now  sum  =   2 ^ n - 1    where n = number of terms.

As number of terms will always log2(N)  because each time  i is divide by 2.

That measn 2 ^  log2(N) - 1 ,    log cancels out .

Left part is N  , Hence overall complexity should ne linear

O(N) is correct answer