The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.5k views

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)$
asked in Algorithms by Loyal (4.3k points)
edited by | 2.5k views
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/2k) * 2  keep n=2k
j= 2(n−1)=n

where did that 1/2 in denominator go

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

5 Answers

+26 votes
Best answer
Answer will be $\Theta(n)$

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

number of iteration will be $2^k = n$ or $k = \log n$

this is in GP find sum till $\log n $,= $\Theta(n)$
answered by Junior (855 points)
selected by
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.
+12 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)

answered by (423 points)
+4 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.
answered by Boss (8.4k points)
+3 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)
answered by Veteran (22.1k points)
0 votes
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)
answered by Veteran (14.3k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
114,271 comments
38,803 users