Official PYQ · 2007Q15Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2007 Q15 — Asymptotic Worst Case Time and Space Complexity

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:

View worked solution

Answer: D

To find the total number of comparisons made by the while loop, we trace the values of $j$ at each step:

Initially, $j = 1 = 2^0$ .
In each iteration, $j$ is doubled: $j = 2^0, 2^1, 2^2, \dots, 2^k$ .

The loop condition is $j \le n$ . The loop terminates as soon as $j > n$ . Let $k$ be the number of successful iterations. For these $k$ iterations, the condition holds true:

2^{k-1} \le n < 2^k

Taking the base-2 logarithm:

k-1 \le \log_2 n < k \implies k-1 = \lfloor \log_2 n \rfloor \implies k = \lfloor \log_2 n \rfloor + 1

Thus, there are $k = \lfloor \log_2 n \rfloor + 1$ successful comparisons where the loop body executes. After these, one final comparison is made where $j = 2^k > n$ , which evaluates to false and terminates the loop.

Therefore, the total number of comparisons is:

\text{Total Comparisons} = \text{Successful Comparisons} + \text{Unsuccessful Comparison} = k + 1 = \lfloor \log_2 n \rfloor + 2

Note: In the original GATE 2007 paper, Option D was printed as $\lfloor \log_2 n \rfloor + 2$ . The $+1$ in the question text is a typographical error, and Option D is the intended correct choice.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2007 Q15 — Asymptotic Worst Case Time and Space Complexity

Related questions