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

d is correct

---

It is D)..

---

flor|logn|+2 is valid for takes the value of n either even or odd

---

i guess if we determine number of iterations than comparisons here it would be an useful analogy

---

This question needs some correction.

---

correct answer should be floor(log n)+2

---

Can you explain

---

When  I am taking n=20 here.No of comparisons performed are 6.

For j=1,2,4,8,16,32 While loop is run

But ceil(20) + 1 = 5.

What am I missing ?

---

@sushmita correct answer will be D . 

and if they ask total no of comparison then answer will be $\left \lfloor log n \right \rfloor$+2

---

@Gurdeep Saini why (A) is not the correct option?

---

@chauhansunil20th take n=3 then you will get 3 from option a and 2 from option d

---

if $n=3$, then following are the comparisons:
$1<=3$
$2<=3$
$4<=3$

what is the issue there are 3 comparisons made by the program @Gurdeep Saini?

 

---

total comparisons is 3

but number of comparisons made in the execution of the loop =2

---

Just 25 days are left and you're playing comment - comment :/
$1<=3 $
$2<=3 $
$4<=3$

Don't you see these 3 comparisons, there are 2 successful and 1 unsuccessful comparisons. total comparisons are 3, and it is not mentioned in the question that we need to count only successful comparisons.

---

do you know what is the execution of loop ?

IF entry condition fail the this will not be count in the execution of loop

---

@Gurdeep Saini If it had asked for the no of comparisons then the answer would have been A ?? As its asking for only no of time's the loop gets executed, so we are not considering the last comparison as then the loop condition fails. (Am I right??)

---

@Rishav_Bhatt no 

then answer will be ⌊log n⌋+2.

---

As question is asking - number Of comparison for which loop executed successfully, that means for last comparison loop doesnt get excuted(unsuccessful) therfore we will not count last comparison.

So , floor(logn)+1 is right.

Option D is correct.

---

Uhmm..why isn’t anybody talking about option C? Isn’t Floor(logn) +1 = Ceil(logn)

---

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

---

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

---

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

---

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