What is the complexity of this piece of code

Question

I had to determinate big O complexity of this piece of code. I thought the answer is nlogn but apparently its n. Can anyone help explain why that is so?

void funct(int n)
{
    for (int i = n; i > 0; i /= 2)
        for(int j = 0; j < i; j++)
            printf("%d\n", j%2);
}

Answer 1

That's geometric progression The first time the inner loop is executed n times. The second time it is executed n/2 times. etc... So we have the sequence: n + n/2 + n/4 + ... + 1 so the final formula is:

n*(1 - (1/2)^(log n))/(1/2)

which is equivalent to n

Answer 2

Look these can be solved using Double Sigma's : Let $ represents sigma. so this problem is :

$(i=n downto 0 by a factor of 2 )$(j=0 to i-1) 1

where 1 represent a unit cost

now for inner sigma its sum of 1 i times that is = i

now problem is $(i=n downto 1 by a factor of 2 ) i

which is sum of i values i.e. n+n/2+n/4+...+1(when n/2^x=1 or after log(n) terms)+0

or n*(1+1/2+.....log(n) terms)

which is a convergent Geometric progression. and the result will be n*(1 - (1/2)^(log n))/(1/2) i.e O(n)

Answer 3

The outer loop, as I'm sure you can see is executed log(n) times. The inner loop is executed on average log(n)/2 times. So the printf statement is executed log(n) * (log(n) / 2) times which equals n / 2. So the complexity of the code is O(n).