Consider the following segment of C code: int j, n; j = 1; while (j <= n) j =…
2018
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.
[log2 n] + 1
- B.
n
- C.
[log2 n]
- D.
[2 log2 n] + 1
Attempted by 184 students.
Show answer & explanation
Correct answer: A
Let the loop run for k successful iterations.
After 0 iterations: j = 2^0 = 1
After 1 iteration: j = 2^1 = 2
After 2 iterations: j = 2^2 = 4
...
After k iterations: j = 2^k
The loop stops when the condition j <= n becomes False. This happens at the (k+1)th comparison.
To find the number of successful iterations (k):
2^k <= n
Taking log base 2 on both sides:
k <= log2 n
The largest integer k is floor(log2 n).
Total Comparisons (कुल तुलनाएँ):
There are k comparisons that evaluate to True (entering the loop).
There is 1 final comparison that evaluates to False (exiting the loop).
Total Comparisons = k + 1 = floor(log2 n) + 1.