Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j =…
2007
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: Base of Log is 2 in all options.
- A.
CEIL(logn) + 2
- B.
n
- C.
CEIL(logn)
- D.
FLOOR(logn) + 2
Attempted by 181 students.
Show answer & explanation
Correct answer: D
Answer: FLOOR(log n) + 2 (log base 2)
Derivation:
Each iteration multiplies j by 2, so after t iterations the value of j is 2^t.
The loop continues while j <= n. If t iterations occur, then the last value of j that satisfied the condition was 2^{t-1}, so 2^{t-1} <= n < 2^t. Therefore t = FLOOR(log2 n) + 1 (this is the number of times the loop body executes).
The condition j <= n is checked one additional time when it fails, so the total number of comparisons is t + 1 = FLOOR(log2 n) + 2.
Example: n = 3. Sequence of j (before body): 1, 2, 4. Comparisons: check 1 <= 3 (true), check 2 <= 3 (true), check 4 <= 3 (false) = 3 comparisons. FLOOR(log2 3) + 2 = 1 + 2 = 3.