Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n;…
2017
Consider the following C function
int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } }
Time complexity of \(fun\) in terms of \(\Theta\) notation is
- A.
\(\Theta(n \sqrt{n})\) - B.
\(\Theta(n^2)\) - C.
\(\Theta(n \: \log n)\) - D.
\(\Theta(n^2 \log n)\)
Attempted by 228 students.
Show answer & explanation
Correct answer: C
Key insight: for a fixed i the inner loop increments j by i, so the number of inner iterations is about n/i.
Step 1: For a given i, j takes values 1, 1+i, 1+2i, … while j < n, so the count is ⌈(n−1)/i⌉ = Θ(n/i).
Step 2: Total work = sum_{i=1..n} Θ(n/i) = n * Θ(sum_{i=1..n} 1/i) = n * Θ(log n) because the harmonic series H_n = Θ(log n).
Conclusion: The time complexity is Θ(n log n).
A video solution is available for this question — log in and enroll to watch it.