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) is not O(f(n))
- B.
f(n) is not O(g(n)) and g(n) = O(f(n))
- C.
f(n) = O(g(n)) and g(n) = O(f(n))
- D.
f(n) is not O(g(n)) and g(n) is not O(f(n))
Attempted by 26 students.
Show answer & explanation
Correct answer: B
The correct answer is Option B. Compare the two functions by taking their ratio: f(n)/g(n) = (n² log n)/(n(log n)¹⁰) = n/(log n)^9. As n grows, n grows faster than any fixed power of log n, so n/(log n)^9 tends to infinity. Therefore f(n) grows asymptotically faster than g(n). Hence g(n) = O(f(n)), but f(n) is not O(g(n)).