GATE CS 2001 Q1.16 — Asymptotic Worst Case Time and Space Complexity

To compare the asymptotic growth rates of the two functions $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$, we can analyze their ratio as $n \to \infty$:

We know that any positive polynomial power of $n$ grows strictly faster than any polylogarithmic power of $n$ as $n \to \infty$. That is, for any constant $k > 0$:

Applying this with $k = 9$:

This indicates that $f(n)$ grows strictly faster than $g(n)$. Consequently:

• $g(n) = O(f(n))$ (since $g(n)$ is asymptotically bounded above by $f(n)$)
• $f(n) \neq O(g(n))$ (since $f(n)$ grows strictly faster than $g(n)$)

Thus, the correct statement is B.