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

best take on why D and not A, clears up everything

https://gateoverflow.in/56129/gate-cse-2007-question-15-isro2016-26?show=59039#c59039

---

take n = 16 (5 times executing) as well as  n = 15 (4 times executing)
option D

---

For n = 5 the no. of comparisons is 4 and by option A I am getting 4 and by Option D i am getting 3 so why option D is marked as correct

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

Here we are calculating the comparisions made while we made it inside the loop not total no of comparisions thats why we for n = 8 the number of comparisions will be 4 .

---

log 16 = [ log 2^4 ]  so for this n = 4

now for this [log 2^4] + 1  for this n = 4+1 = 5

so the answer is  D
 

---

Your logic to use floor(log(n)) + 1 is incorrect here. But the method you use leads to the correct answer as well. The answer is indeed floor(log(n)) + 2. But since floor(log(n)) + 2 is not provided in the options, the other option which is EXACTLY equal to floor(log(n)) + 2 is ceil(log(n)) + 1. I graphed both functions in Desmos and the graph is exact. So the answer should be option A) ceil(log(n)) + 1

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

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

Answer 5

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

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

Answer 6

Answer D). Log₂n + 1

Comments

then, also D.

why logn + 2?

---

for successfull comparisons, 

take n = 9

1,2,4,8 are only successful, so , it should be C).

In this case , I thought you got option C as ans if it is asking for successfull comparisons. So I told you to check it for n=8, and it does not satisfy.

But in my first comment, i said that if it is asking for only successfull comparisons then option D is okay but it is not mentioned in the question right.

So here exact ans should be |_log n _| + 2 which is clearly explained by @vikrant sir in below answer.

---

ambigous answer