GATE CSE 2007 | Question: 15, ISRO2016-26

Question

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:

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

• B. $n$

• C. $\lceil \log_2n \rceil$

• D. $\lfloor \log_2n \rfloor +1$

Comments

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

---

What's the difference between option A.) & D.)

---

take i/p and check for D option u will get lesser value as we are taking floor and in Op A we will get higher value as ans for any i/p.

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

Comments

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

---

No option a is not correct. Check at j=8. The number of comparisons are 5 (1,2,4,8,16). But option a is giving only 4.

Answer 2

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

Comments

ambiguous ques

---

@Sarvottam patel , your answer saved my day.

---

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

Answer 3

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

Comments

@ Arjun  Sir, Please check this solution

---

leen sharma I am agree with you

---

option A is correct check it

---

@LeenSharma option D is correct because in the question it tells find number of comparision made in the execution of the loop hence for last comparision where loop terminate will not be counted in the answer because it doesnot satisfy the statement “Execution of loop”.plz correct me if i am wrong.

Answer 4

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

The correct answer to this is -  ⌊log₂n⌋ + 2