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

due to the line "in the execution of the loop" the answer is D.

if total comparisons were asked then it will be floor (logn) +2

Answer 2

Answer is option D

I look an array and tried to look how j changed.

Answer 3

let n=8, then then value if j that would get compaired are 1,2,4,8...number of comparison=4

upper_bound( ln8 ) +1 = 4

let n=6, then number of comparison = 3

upper_bound( ln6 ) +1 = 3

which are satisfied by option A

Comments

I think answer should be (a) because more values of "n" are satisfied by this option. Only when "n" is power of 2, This option will not give the correct answer.

---

@Kapil A) is not the answer. Try for n=8

---

it would not b ln as ln is base e

it would be log(n) base 2 as we are multiplynh by 2 each time

so for any number expect powers of 2

ans would be upper bound(log(n) base 2)+1