Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j =…
2016
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.
|_ log 2n _| * n
- B.
n
- C.
|_ log2n _|
- D.
|_ log2n _| + 1
Attempted by 179 students.
Show answer & explanation
Correct answer: D
The loop variable j starts at 1 and doubles each iteration (j = 2^0, 2^1,...). The while condition is checked before every loop body execution and one final time when the loop terminates. If the loop runs k times, then 2^k <= n, which means k = floor(log₂n). Including the final failed check that stops the loop, total comparisons equal k + 1 = floor(log₂n) + 1. Option C misses the final check, while A and B incorrectly multiply or linearize the logarithmic growth. Thus, Option D correctly accounts for all comparisons.