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

---

@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

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 2

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

Answer 3

We have to find the number of comparisons made in the execution of the loop. So, counting the no. of comparisons for which the loop executes. With this fact lets observe what happens to the value of j at each iteration.

---

Iteration No. 'i'	Value of j at ith iteration
1	1
2	2
3	4
4	8
5	16
...	...
k	2k-1

Lets assume that k^th iteration is the last successful iteration of the loop  after which the value of j crosses n.Therefore,

2^k-1 > n should hold.

k-1 > log₂n

k > log₂n + 1

k = ⌈log2n⌉  + 1

Option A seems correct.

Correct me if I am wrong!!!

Comments

I think, u have assign wrong operator,

$2^{k-1 }\leq n$

$k-1 \leq n$

$k - 1 = \left \lfloor \log n \right \rfloor$

$k = \left \lfloor \log n \right \rfloor +1$

Hence option D is correct

Answer 4

It should be ⌊logn⌋+2

⌊log2n⌋+1

⌊log2n⌋+1