GATE CSE 2006 | Question: 15

Question

Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. 

 for( i = n, j = 0; i > 0; i /= 2, j +=i );

Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? 

• A. $val(j)=\Theta(\log n)$
• B. $val(j)=\Theta (\sqrt{n})$
• C. $val(j)=\Theta( n)$
• D. $val(j)=\Theta (n\log n)$

Comments

instead of j += i, if it was simply j++, then the value of j will be floor(logn) + 1, which is Theta(logn)

---

@Manu Thakur

in the given example 

value of j is increment after the value of i decrement.

value of k is increment before the value of i decrement.

---

Why is n= 2**k ? Why not k = n. Then T(n) changes !

Since i = i/2. The total no of terms will be logn in the GP series.

Answer 1

I hope it helps!

Answer will be option C.

Answer 2

C is the answer.

$\frac{n}{1}+\frac{n}{2}+\frac{n}{2^{2}}+....+\frac{n}{2^{logn}} = n(1+\frac{1}{2} +\frac{1}{2^{2}}+....+\frac{1}{2^{logn}})\Rightarrow \Theta (n)$

Answer 3

For n =4 j is getting added 3 times For n =8 j is getting added 4 times For n =16 j is getting added 5 times so we can see that the number of times j is getting added is (log n +1) so its THETA(log n)

Answer 4

O(n) is the answer