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

@Daal_bhaat_enjoyer log n = (1 + 1/2 + 1/3 + 1/4 + ...)

---

if j++ is given instead of j+=i, then θ(log n) will be correct right?
 

---

Check this

Answer 1

Answer will be $\Theta(n)$

$j = n/2+n/4+n/8+\ldots +1$

$\quad = n \left[1/2^1 + 1/2^2 + 1/2^3 +\ldots + 1/2^{\lg n}\right] $

(Sum of first $n$ terms of GP is $\left[a . \frac{1-r^n}{1-r}\right],$ where $a$ is the first term, $r$ is the common ratio $< 1,$ and $n$ is the number of terms)

$\quad = n \left[1/2 \frac{1 - (1/2)^{\lg n}}{1-1/2} \right]$

$\quad = n \left[\frac{n-1}{n}\right]$

$\quad = n-1 = \Theta(n)$

Comments

j = n/2+n/4+n/8+...+1

this is log series doesn't it ?

Then how are you getting theta(n) ?

Will it not be  thetha ( log n ) ?

---

j=n/2+n/4+n/8----+1

j=n*(1/2+1/4+1/8-----1/n)

j=n*(1-1/n)

j=n-1

so O(n)

---

what will be the value of n ?? only n=2^a ones?? i think it will be after applying gp

n.(1-1/2^n)

hence O(n) .... n/2^n will neglected  for bigger value of n ...

---

@puja_mishra,

$\begin{align*} f(n) & = \frac{n}{2}+\frac{n}{4}+\frac{n}{8}+.....+\frac{n}{2^{k}} \\ & = n \sum_{i=1}^{k}\frac{1}{2^{i}} \\ & = n (1-\frac{1}{2^{k}}) \\ & = n- \frac{n}{2^{k}} & [ \text{where} \ n=2^{k}] \\ & = n-1 \end{align*}$

Which is $O(n)$

---

this explanation is wrong , wrongly selected as the best answer .

---

Then wat will be the ans??

---

Answer is correct , the explanation is not correct .. Val (j) grows linearly .. like this

For i=16

i=8   j=8

i=4   j=12

 i=2   j=14

i=1   j=15

And finally , i= 0.

It's explained in the answer below .. that is more apt .

---

Just a small note,

in the $for$ loop

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

if we have 

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

the answer might vary as then $j$ would be incremented first with $i's$ initial value

So if $n= 2^k$ where $k = 4$,we get 

$j=15$ in the first case.

and

$j=31$ in the second.

---

yes .... log n series is

(1 + 1/2 + 1/3 + 1/4 + 1/5 + .....1/n) not (1 + 1/2 + 1/4 + ....)

---

I have come to similar answer but for G.P. sum which formula you guys are using? I used  a{r^{n} - 1}/{r - 1} and finally got j = 2n-2 which is O(n) so answer comes same. But what formulae you guys used? I know its a trivial question but please help.

Answer 2

is correct because i gets reduced log2(n) time  say for eg

  i=16 than 

  i=8   j=8

  i=4   j=12

   i=2   j=14

   i=1   j=15

   i=0 

hence 

Answer 3

The variable j is initially 0 and value of j is sum of values of i. i is initialized as n and is reduced to half in each iteration. j = n/2 + n/4 + n/8 + .. + 1 = Θ(n) Note the semicolon after the for loop, so there is nothing in the body.

Comments

Thanks for giving information about semicolon I can't view that

---

nice explanation

Answer 4

j=n/2+n/4+n/8----+1

j=n*(1/2+1/4+1/8-----1/n)

j=n*(1-1/n)

j=n-1

so O(n)

Comments

what formula of gp is used?

Answer 5

I hope it helps!

Answer will be option C.

Answer 6

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)$