Time Complexity

Question

Consider the following code . What should be the time complexity?
j = n  ;

while (j >= 1){    

 for (i = 1 to j    )   

   x = x + 1    ;

 j = n/2 ;

 }
 

(A)O(logn)
(B)O(n logn)
(C)O(n )
(D)None of the above

Comments

@srestha oppps It will be $O(2n)$, then it becomes $O(n)$. dude i need a lot of learning :P Thanks srestha, you are a jem. :D

---

yes srestha...i think...i wud be o(n) u r right

---

yes I missed it too

it will be 2^logn-1/(2-1) =O(n)

Answer 1

The only thing which you need to care is that $j = \frac{n}{2}$ this will not allow this program to terminate if $n > 1$

j = n;
while (j >= 1){
    for (i = 1 to j)
        x = x + 1;
    j = n/2;           // If n > 1 then J will always be greater than 
                       // or equal to 1, hence this loop will not terminates. 
}

Hence Answer will be D) None of the above

Thanks @manojK

Comments

offcourse you are right now,,

if it would have been

j=j/2 then answer would be logn

everybody committed mistake

---

@Tauhin Dude what is the addition of this series..

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

How it can be $O(logn)$. 

Dude, can not you see the first term $n$ so how it can be $O(logn)$.?? 

---

Please can you give detailed explanation of the above code. It is going above my head. Utterly confused on the explanation tat u've given. It'll be b8r if u go for line by line detailed explanation of each line of the code.

Answer 2

Outer while loop will run O(log n) times

inner loop for each iteration of outer loop will run

when j=n inner loop will run n times

"       j=n/2  "     "      "    "  n/2  "

 "      j=n/4  "      "     "   "   n/4  "

.

.

.

"      j=2   "     "    "    "   1   "

inner loop will total run =1+2+4+ .......+n/4+n/2+n

                                = 1(2ⁿ -1) /(2-1) =O(2ⁿ)

Comments

sherstha dear u r getting the right series but wrong answer...

1+2+4.......2^k

then for what value of k

2^k=n

check it once

Answer 3

for (i=1 to j) => j=n => so runs n times

=>j=n/2 so runs n/2 times

=>j=n/8 so runs n/8 times

So, it runs, n+n/2+n/8+n/16+.........1

Calculating it, we get O(n) times.

Comments

it's a geometric series

why u r not applying S= a(rⁿ-1)/(r-1)