Suppose f(n)=n^2 logn. Consider the statements:
2022
Suppose f(n)=n^2 logn. Consider the statements:
- A.
A, B & C are all not true.
- B.
B & C are true but A is not true.
- C.
B is true but A & C are not true.
- D.
A & B are true and C is not true.
Attempted by 371 students.
Show answer & explanation
Correct answer: C
Given f(n) = n^2 log n.
Compare with n sqrt(n) = n^{3/2}: (n^2 log n)/(n^{3/2}) = n^{1/2} log n → ∞, so f(n) grows faster than n sqrt(n) and therefore is not O(n sqrt(n)).
Compare with n^2 sqrt(n) = n^{5/2}: (n^2 log n)/(n^{5/2}) = (log n)/n^{1/2} → 0, so f(n) is asymptotically smaller and hence f(n) = O(n^2 sqrt(n)).
Compare with n^3: (n^2 log n)/n^3 = (log n)/n → 0, so f(n) = o(n^3) and therefore f(n) is not Ω(n^3).
Conclusion: The only true statement is that f(n) = O(n^2 sqrt(n)). The other two statements are false.