edited by
36,739 views
64 votes
64 votes

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
    j = j * 2;

The number of comparisons made in the execution of the loop for any $n > 0$ is:

  1. $\lceil \log_2n \rceil +1$

  2. $n$

  3. $\lceil \log_2n \rceil$

  4. $\lfloor \log_2n \rfloor +1$

edited by

15 Answers

7 votes
7 votes
Answer is a)

say n=4
According to answer d no of comparisons will be 3
but actually there will be 4 comparison
1<=4
2<=4
4<=4
and final comparison will be 8<=4 which will give false ,So total no of comparisons are 4 So d cant be true

Moreover say for 7 node no of comparisons will be
1<=7
2<=7
4<=7
8<=7 i.e also 4
so answer is ceil (logn)+1 i.e option a
6 votes
6 votes

Answer D). Log2n + 1

5 votes
5 votes

We have to find the number of comparisons made in the execution of the loop. So, counting the no. of comparisons for which the loop executes. With this fact lets observe what happens to the value of j at each iteration.


Iteration No. 'i'   Value of j at ith iteration
1 1
2 2
3 4
4 8
5 16
... ...
k 2k-1

Lets assume that kth iteration is the last successful iteration of the loop  after which the value of j crosses n.Therefore,

2k-1 > n should hold.

k-1 > log2n

k > log2n + 1

k = ⌈log2n⌉  + 1

Option A seems correct.

Correct me if I am wrong!!!

4 votes
4 votes

It should be ⌊logn⌋+2

log2n+1

log2n+1

edited by
Answer:

Related questions

27 votes
27 votes
4 answers
1
Kathleen asked Sep 21, 2014
33,744 views
The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is:$11001001000$$110010010...
33 votes
33 votes
4 answers
3