Time Complexity : ME OTS

Question

Comments

O(n)??

---

@Gate Fever 

yes, explain please.

Answer 1

when i=n ; j goes n times

when i=n/2; j goes n/2 times

when i=n/4 ; j goes n/4 times 

how many time loop for i goes ?? its logn times

so 

complexity comes out to be 

n+ (n/2)+(n/4) +(n/8)+(n/16)+..........logn times

=n[1+ (1/2)+(1/4)+(1/8)+......................logn terms](taking n common )

{since 1+ (1/2)+(1/4)+(1/8)+......................logn = constant  (u can find this by applying GP fromula)}

=n*1

=O(n)

Comments

@himgta 

---

1+ 1/2+1/4+1/8+.....+logn

formula is a(1-r)/(i-r^n)

here a=1,r=1/2; n=logn

therefore

=$\frac{1-1/2}{1-(1/2)^{logn}}$

=$\frac{1/2}{1-2^{-logn}}$ {logn has base 2; sorry i am using latex first time so i dont know how to write that in it}

=$\frac{1/2}{1-n^{-log2}}$

=$\frac{1/2}{1-n^{-1}}$

$\frac{1/2}{1-\frac{1}{n}}$

=$\frac{n}{2(n-1)}$

=1/2 = constant

hope it clears your doubt

---

@Gate Fever

@HeadShot

thanks..I got it!