edited by
36,697 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

Best answer
88 votes
88 votes
$$\begin{array}{|c|l|c|} \hline \text{n} & \text {No. of comparisons} & \text{$\lfloor \log_2 n\rfloor + 1$}\\\hline \text{1} &  \text{$2 \;(j = 1,2)$} & \text{1}\\\hline \text{2} & \text{$3\; (j = 1,2,4)$} & \text{2} \\\hline \text{3} & \text{$3\; (j = 1,2,4)$} & \text{2} \\\hline \text{4} & \text{$4 \;(j = 1,2,4,8)$} & \text{3} \\\hline  \text{5} & \text{$4\; (j = 1,2,4,8)$} & \text{3} \\\hline \end{array}$$
We have to count those comparisons which happens during the execution of the loop and so the exit comparison must also be a part. So, the correct answer should be $\lfloor \log_2 n \rfloor + 2.$

Since this is not in the choices we can assume that the question setter excluded the exit comparison and so the answer should be  $\lfloor \log_2 n \rfloor + 1.$

Option D.
selected by
21 votes
21 votes
Assuming that "comparisons made in the execution of the loop" means that comparison made while loop is executing, last comparison is not counted.

Say we have j = 7.

Then successful comparisons are 1,2,4. (We get out in next comparison.) So 3 comparisons

Then

A) Incorrect as We get 21 !=3.

B) Incorrect, this is 8.

C) Correct

D) Correct

C & D both gave 3

In C & D for tie breaking, we can take j = 8. No of comparisons (Successful) -> 1,2,4,8.(We get out of loop in 16)

C) 3 != 4. Incorrect

D) 4 Correct

 

Answer -> D
17 votes
17 votes
n Number of Comparisons   
1 2(j=1,2)  
2 3(j=1,2,4)  
3 3(j=1,2,4)  
4 4(j=1,2,4,8)  
5 4(j=1,2,4,8)  

Answer should be None of these here.I think Answer should be $\lfloor \log_2n \rfloor +2$ .

edited by
9 votes
9 votes

All the options fail for n = 2, 4, 8, 16... 

The correct answer to this is -  ⌊log2n⌋ + 2

Answer:

Related questions

27 votes
27 votes
4 answers
1
Kathleen asked Sep 21, 2014
33,731 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