4.6k 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)$
edited | 4.6k views
0
All the answers are wrong though it is selected as best answer!

correct it some one .
0
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
+10

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$

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?

0
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)
0
Its not the case of summation till infinity.

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
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 ) ?
+17
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 ...
+17
@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 .
+1

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.

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

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.
0
Thanks for giving information about semicolon I can't view that
0
nice explanation
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)
0
what formula of gp is used?
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)

I solved it like this:

i= 32, so j = 16+4+2 = 22

22 is not around log32, also not around 32log32, also not around sqrt(32), so only thing remaining is theta(n), also its theta and not big O.

1
2