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 solved it like this:

i= 32, so j = 16+4+2 = 22

22 is not around log32, also not around 32log32, also not around sqrt(32), so only thing remaining is theta(n), also its theta and not big O.

 

Comments

When i = 32, j is 31, not 22.

i = 32	i = 16	i = 8	i = 4	i = 2	i = 1	i = 0
j = 0	j = 16	j = 24	j = 28	j = 30	j = 31	j = 31***

*** means break out of the loop, as condition has failed.

Answer 2

I hope you guys got this now