Let f(n) = n² log n and g(n) = n (log n)¹⁰ be two positive functions of n.…
2001
Let f(n) = n² log n and g(n) = n (log n)¹⁰ be two positive functions of n. Which of the following statements is correct?
- A.
f(n) = O(g(n)) and g(n) ≠ O(f(n))
- B.
f(n) ≠ O(g(n)) and g(n) = O(f(n))
- C.
f(n) = O(g(n)) but g(n) = O(f(n))
- D.
f(n) ≠ O(g(n)) but g(n) ≠ O(f(n))
Attempted by 81 students.
Show answer & explanation
Correct answer: B
To compare growth rates, evaluate the limit of f(n)/g(n) as n approaches infinity.
This simplifies to n/(log n)^9. Since polynomial growth dominates logarithmic growth, the limit is infinity.
Thus, f(n) grows strictly faster than g(n), meaning g(n) = O(f(n)) and f(n) ≠ O(g(n)).
A video solution is available for this question — log in and enroll to watch it.