The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 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?

- $val(j)=\Theta(\log n)$
- $val(j)=\Theta (\sqrt{n})$
- $val(j)=\Theta( n)$
- $val(j)=\Theta (n\log n)$

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

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

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

can someone help

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

+26 votes

Best answer

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

this is log series doesn't it ?

Then how are you getting theta(n) ?

Will it not be thetha ( log 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 ...

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

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

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 .

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.

+12 votes

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users