Consider the following function: int unknown(int n){ int i, j, k=0; for…
2013
Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is
- A.
\(Θ(n^2) \) - B.
\(\Theta(n^2\log n)\) - C.
\(\Theta(n^3)\) - D.
\(\Theta(n^3\log n)\)
Attempted by 165 students.
Show answer & explanation
Correct answer: B
Count the number of times the statement k = k + n/2 executes and the amount added each time.
Outer loop: i goes from n/2 to n inclusive, so the number of iterations is n - n/2 + 1 = n/2 + 1 = Θ(n).
Inner loop: j takes values 2, 4, 8, ..., up to n. The number of iterations is the number of powers of two ≤ n, which is floor(log2 n) = Θ(log n).
Work per inner iteration: each time k is increased by n/2, which is Θ(n).
Combine these factors:
Number of times the addition happens = (number of outer iterations) × (number of inner iterations) = Θ(n) × Θ(log n) = Θ(n log n). Each addition contributes Θ(n), so
Total k = Θ(n) (per-addition) × Θ(n log n) (number of additions) = Θ(n^2 log n).
Therefore, the function returns a value that grows as Θ(n^2 log n).
A video solution is available for this question — log in and enroll to watch it.