Project ForgeAlgorithms
Complexity Analysis
GATE 2007
Medium
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₂ n⌉ + 1
- Bn
- C⌈log₂ n⌉
- ⌊log₂ n⌋ + 1
Explanation
j takes the values 1,2,4,...,2^k while j≤n. The number of times the loop body executes (i.e. the number of successful comparisons) is the count of powers of 2 from 2^0 up to the largest power ≤n, which is ⌊log₂ n⌋+1. E.g. n=4: j=1,2,4 all pass (3 = ⌊log₂4⌋+1=2+1=3) before j=8 fails.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.