edited by
19,205 views
35 votes
35 votes

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? 

  1. $val(j)=\Theta(\log n)$
  2. $val(j)=\Theta (\sqrt{n})$
  3. $val(j)=\Theta( n)$
  4. $val(j)=\Theta (n\log n)$
edited by

10 Answers

Best answer
56 votes
56 votes
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)$
edited by
21 votes
21 votes

val(j)=\Theta( n)

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 val(j)=\Theta( n)

10 votes
10 votes
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.
5 votes
5 votes
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)
Answer:

Related questions

90 votes
90 votes
12 answers
4