Consider the following C-program fragment in which i, j and n are integer…
2006
Consider the following C-program fragment in which i, j and n are integer variables.
for (i = n, j = 0; i >0; i /= 2, j += i);
Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
- A.
val(j) = Θ(logn)
- B.
vaI(j) = Θ(sqrt(n))
- C.
val(j) =Θ (n)
- D.
val(j) = Θ(nlogn)
Attempted by 123 students.
Show answer & explanation
Correct answer: C
Answer: val(j) = Θ(n).
Reasoning:
The loop initializes i = n and on each iteration does i /= 2 and j += i, so the terms added to j are n, floor(n/2), floor(n/4), ... down to 1.
Upper bound: The geometric series satisfies n + n/2 + n/4 + ... < 2n, so j = O(n).
Lower bound: The first term is n, so j ≥ n, giving j = Ω(n).
Combining the bounds gives j = Θ(n).