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

All the answers are wrong though it is selected as best answer!

correct it some one .

---

C is correct answer.

---

i did not understand step 2 here

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

step  2 -  j=n*(1-1/n)

can someone help

---

simplify the for loop:
j=0;
for( i=n; i>0; i=i/2)
{
j = j+i;
}

$j = 0 + n + n/2 + n/2^2 + n/2^3 + ................. n/2^k$
$j = n*(1 + 1/2 + 1/2^2 + 1/2^3 + .......... 1/2^k) $
$n = 2^k$
$j = n*\frac{( 1 - (1/2)^k)}{1-1/2}$
$j = n*\frac{( 1 - 1/2^k)}{1/2}$
$j = ( n - n/2^k)$  keep $n=2^k$
$j = n -1 = n$

Answer is (C).

---

@manu

j=n∗(1−(1/2)k)1−1/2

what formula have you used here ?

---

it's a G.P series of k terms where r=1/2 and r <1

---

@manu shouldnt it be

j=(n−n/2^k) * 2  keep n=2^k
j= 2(n−1)=n

where did that 1/2 in denominator go

---

@Manu Thakur pC how to analyze that n=2^k?

---

If we calculate in terms of time complexity, we can do summation till infinity.

sum of G.P till infinite = A/1-r

A=1/2,  r= 1/2

=O (n)

---

Its not the case of summation till infinity.

---

It is the case of summation till infinity when i is real but it is given that i is integer so finite summation

---

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.

---

as we all know ..

n * (1/2 + 1/4 + 1/8 + 1/16 + 1/32...... 1/2^k) , where 2^k = n...

so why can't we jus put log2n in place of the series, since we know that the sum of harmonic series is log2n..

so answer would be θ(nlog2n)

---

@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

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