25,497 views

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$

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

edited

@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.

@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.$

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

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

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

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. :(
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

ambiguous ques

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

 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

@   Sir, Please check this solution

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

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

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