What is the worst case time complexity of this function?

Question

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;
}

Answer 1

Outer loop executes $\log{n}$ times ...

For $i=n$, inner loop will execute $n$ times.

For $i=\frac{n}{2}$, inner loop executes $\frac{n}{2}$ times. And so on...

count+=1 statement is in the inner loop, and will be executed $n + \frac{n}{2} + \frac{n}{4} + \ldots + 1$ times.

Solving,

$\underbrace{n + \frac{n}{2} + \frac{n}{4} + \ldots + 1}_{\log{n} \text{ terms}}$

$= n \cdot \frac{1- (1/2)^{\log{n}}}{1/2}$        (using GP, first term $=1$ and common ratio $=1/2$)

$=2n(1-\frac1 n) = 2n - 2$

complexity $=O(n)$

Comments

plz correct me ,I think there are logn+1 terms

Answer 2

The worst case time complexity of this function is O(n)..... the outer loop iterates for O(logn) as the value of n is changing like this.....n,n/2,n/4......1(assuming n is power of 2). Therefore say the ith term will be n/2^(i-1)...now equating this to 1 we get i as O(logn). Hence the number of iterations of the outer loop(the total number of terms in the series) is O(logn). Now for each iteration of the outer loop the inner loop is iterating depending on the value of i i.e for 1st iteration of outer loop inner loop is iterating n times, for 2nd iteration of the outer loop inner loop is iterating n/2 times ..like..this. Therefore the total time complexity becomes ...n+n/2+n/4+.....+1(assuming n power of 2)......therfore, its the sum of g.p series with logn number of terms in it....hence the sum becomes 1.(2^(logn)-1)/(2-1)...which equates to O(n)...

Comments

@Radha Gogia : In your G.P., 1st term is 1, common ratio is 1/2, and number of terms is log n (I think you are doing wrong in this part).

So (1+1/2+...+1/n) = $\frac{1*\left(1-\left(\frac{1}{2}\right)^{log n}\right)}{1-\frac{1}{2}}= n-1$
 

---

How did u get n-1 , (1/2) ^ log n is evaluated as 2^-log n = 1/n , stucked up .

 

12)

---

Sorry I forgot to multiply by n which we have taken common. Also number of terms is exactly $log n+1$.

For example, if series was 1+2+4+8, then here n is 8, and log n is 3, but we have 4 terms.

n*(1+1/2+...+1/n) = $n*\frac{1*\left(1-\left(\frac{1}{2}\right)^{log n+1}\right)}{1-\frac{1}{2}}= 2n*\left(\frac{2n-1}{2n}\right)$

$=2n-1$, which is O(n)