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

No one is right option .

n=2 comparision done 3

n=4 comparision done 4

n=5 comparision done 4

n=6 comparision done 4

Comments

When you take n=7 we get 3 successful comparisons during execution. So option D is true. When we take n=5 option B and D are eliminated.

Answer 2

For n=1, loop execution for success = 1, for failure = 1

n=2, for success = 2 for failure =1

n=3, for success = 2 for failure =1

n=4, for success = 3 for failure = 1

..

Now if you consider no. of comparison for while execution excluding failure condition answer should be D($\left \lfloor logn \right \rfloor +1$)

otherwise with failure condition answer should be ($\left \lfloor logn \right \rfloor +2$)

Comments

(floor(log n)+1) (option (D)) is same as ceil(log n) (option (C))

(floor(log n)+2) is same as (ceil(log n) + 1).

Seems to me, the answer should be (A).

The question asks for the number of comparisons, not the number of comparisons which evaluate as "true", so why would we think of excluding the last comparison, when the answer corresponding to the correct one, is already in the options?

 

You can try running this code to verify:--

    int j,n;
    int count;
    for(n=1;n<100;n++)
    {
        count=0;
        j=1;
        while(1)
        {
            count++;
            if(j>n)
                break;
            j=j*2;
        }
        double x=log((double)n)/log(2);
        int case1 = ceil(x) + 1;
        int case2 = floor(x) + 1;
        printf("n=%d, Actual=%d, Floor=%d, Ceil=%d\n",n,count,case2,case1);
        if(case1==count)
            printf("Correct\n\n");
        else
            printf("\n");
    }

//case1 matches actual comparison count for all cases except for the numbers which are powers of 2, while case2 matches none.

Answer 3

n is compared with 2⁰, 2¹ , ........ 2^floor(lgn) , 2^{floor(lgn) + 1}

So 0 to floor(lgn) + 1, and the expression always evaluates to false for j =  floor(lgn) + 1,

Hence, in both the cases floor(lgn) + 2 comparisons are made

Here is an example to make things clearer:

.We need to consider two cases

1) When n = 2^k   

        Take 8 . (1<=8),(2<=8),(4<=8),(8<=8),(16<=8)

        five comparisons are made.

2) When  n != 2^k 

      Take 11.  (1<=11),(2<=11),(4<=11),(8<=11),(16<=11)

      Again five comparisons are made . 

Comments

By taking the different -2  e.g. now i completely confused either it should be a ) or d ) please tell me .It seems option a)is the strongest answer rather than d) .

 

Please anyone help me. 

@Shaik Masthan sir!

---

option a is correct !

---

Thank you , sir its helps me to get rid of my frustration.

Answer 4

Value of j is updated as: 1,2,4,8,16,...,(2^k)

Condition for which loop will be executed:

         j <= n

         2^k <= n

         k <= log n

         k = ⌊logn⌋ 

Number of times loop will be executed: (k+1) i.e (⌊logn⌋ +1)

Number of times comparisons will be made: (Number of times loop will be executed + 1) i.e. (⌊logn⌋ +2)