in Algorithms edited by
25,497 views
56 votes
56 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$

in Algorithms edited by
by
25.5k views

4 Comments

@kirtipurohit If logn is integer then it is not true.

0
0
edited by

@Abhrajyoti00 what should be the ans?

no. of comparison exactly 4 aa rhi h rit for n=5? so log 5 base 2= ceil of 2.32+1=4 that is total no. of comparison and if we consider floor then ans should be floor logn+2. but in this question only no. of comparison are counted with execution of statement j=j*2: so last comparison not included because 8<=5 is not true so stmt j=j*2 not executed so the ans is d. 

0
0

@Nisha Bharti Yes, you are right,

Actually answer is $\lfloor \log_2 n \rfloor + 2$ if we even include the exit condition.

But here the options don't have $2$ at last, which means that we don’t need to calculate the exit condition.

Thus the answer is Option D) $\lfloor \log_2 n \rfloor + 1.$

1
1

15 Answers

78 votes
78 votes
Best answer
$$\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

4 Comments

If we consider entry and exot comparison than option A is also right
0
0

@ankit3009 Can you help me with this (A) seems correct to me.

1
1
The question isn’t framed well as it doesn’t match any of the options. And we can’t really assume the case what question setter wants. :(
2
2
19 votes
19 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

4 Comments

ambiguous ques
0
0
@Sarvottam patel , your answer saved my day.
0
0

@Akash Kanase sir , is the statement "made in the execution of the loop" the catch here ? 

0
0
15 votes
15 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

3 Comments

edited by

@ Arjun  Sir, Please check this solution

0
0
leen sharma I am agree with you
0
0
option A is correct check it
0
0
8 votes
8 votes

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

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

Answer:

Related questions