The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.8k 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 Active (3.7k points)
edited by | 2.8k views
0
All the answers are wrong though it is selected as best answer!

correct it some one .
0
C is correct answer.
0
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
+3

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

0
@manu

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

what formula have you used here ?
+1
it's a G.P series of k terms where r=1/2 and r <1
0

@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

0

@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/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)$
answered by Junior (805 points)
edited by
0
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 ) ?
+16
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)
+2
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 ...
+13
@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)$
–1
this explanation is wrong , wrongly selected as the best answer .
0
Then wat will be the ans??
0
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 .
0

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.

+1

yes .... log n series is

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

0
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 (411 points)
+5 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 Loyal (8.6k points)
0
Thanks for giving information about semicolon I can't view that
+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 Boss (20.4k 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 Boss (14.1k 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

35,526 questions
42,803 answers
121,618 comments
42,166 users