Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0;…
2015
Consider the following C function.
int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2) ++q; } return q; }
Which one of the following most closely approximates the return value of the function fun1?
- A.
\(n^2\) - B.
\(n (log \ n)^2\) - C.
\(n \ log \ n\) - D.
\(n \ log(log \ n)\)
Attempted by 192 students.
Show answer & explanation
Correct answer: D
Key insight: count how many times each loop runs and multiply.
Outer loop: i runs from 1 to n-1, so it executes Θ(n) times.
Middle loop: j starts at n and is divided by 2 until j ≤ 1, so p becomes Θ(log n).
Inner loop: k starts at 1 and is doubled until k ≥ p, so it runs Θ(log p) = Θ(log log n) times.
Conclusion: Each outer iteration increases q by Θ(log log n), so the total returned value q is Θ(n log log n).
A video solution is available for this question — log in and enroll to watch it.