time complexity closed

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

 

what is the time complexity

Answer 1

i =n   n/2      n/4    n/8  ....................logn times
j=n     n/2     n/4    n/8 ...........logn tmes

T(n) = n+ n/2 + n/4 + n/8 + ...........logn time
       = n(1+ 1/2 + 1/4 + .............logn times) Decreasing GP
         =O(n)

Comments

T(n)=n+ n/2 + n/4 + n/8 + ..........+1

T(n)=n+ n/2 + n/4 + n/8 + ..........+n/n

T(n)=n(1+1/2+1/4+1/8+......+1/n)

say it takes k iterations to reach 1 then loop stops so..

T(n)=n(1/2^0+ n/2^1 + n/2^2 + n/2^3 + ..........+1/2^k)

n=2^k

k=log2n

so it's time complaxity should be lon2n

---

https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF

1/2+1/4+1/8+...infinity=1

Hence complexity should be O(n).

---

1+1/2+1/4+1/8+1/16    all these two powers will   wind up to a Geometric series  where the value will be 1

so n(1+1/2+1/4+1/16….1/n) =n(1)=O(N)

Answer 2

Time Complexity of the above algorithm $=$No of times " $count+=1$ " executes.Following Table gives better picture$\Rightarrow$

 

i	j
$N$	$N$
$N/2$	$N/2$
$N/4$	$N/4$
$\vdots$	$\vdots$
$N/N$	$N/N$

$\Rightarrow \, T\left ( N \right )=\left ( N/1+N/2+N/4 \cdots N/N \right )$

                             =$N\left ( 1/1+1/2+1/4 \cdots 1/N \right )$

    $\left ( 1/1+1/2+1/4+\cdots 1/N \right ) =\sum_{k=0}^{k=n} 1/2^{k}$

solving it ,we can say that  $\sum_{k=0}^{k=n} 1/2^{k} < < < \sum_{k=0}^{k=\infty } 1/2^{k}$

$\sum_{k=0}^{k=\infty } 1/2^{k}$=$1/\left ( 1-\left ( 1/2 \right ) \right )=2$

$\therefore \sum_{k=0}^{k=n } 1/2^{k}  \approx \Theta \left ( k \right )$                              

$T\left ( N \right )=\Theta \left ( N*\left ( \Theta \left ( k \right ) \right ) \right )$

$T\left ( N \right )=\Theta \left( N \right )$

Comments

@Akriti sood yes, and the sum of this GP series will be 1( 1 - (1/2)^k)/1 -1/2. therefore answer is O(n)

---

My bad ! @akriti @vijay ..i didn't observed that it is growing like 1/2,1/4,1/8... rather i observed wrongly like 1/2,1/3,1/4,1/5.....making it a harmonic number and then making its sum as log n ...updated my answer

---

Hey guys :(,  i am getting a really wierd answer please can anyone explain where i am getting it wrong.

Answer 3

Here lets take eg :

LET n = 10

initially: i  = 10 (first loop)

               j = 0 < 10(i) so it will loop from 0 to 9 times

NOW AFTER NESTED LOOP GETS OVER THIS TAKES PLACE

  i /= 2

SO value of i = 5 (first loop ) 2 iteration.

this time j will run from     j = 0 < 5(i) so it will loop from 0 to 5 times

each time value of i will be divided by 2 and similarly for corresponding value of j will iterate from 0 to i/2 times.

so, T(n) = O(n + n/2 + n/4 + … 1) = O(n) for j (This is for iteration of j only )

i               j

10           0-9 times

5              0 - 4 times

2             0 - 1 times

similarly value of j which was initially n i.e 10  gets decreased in order on n/2 forming GP & thus we get O(n)

Answer 4

Follow this-->

https://stackoverflow.com/questions/33676979/time-complexity-of-fun