Why is $n \log (n)$ more significant than $n^2 \log (n)$ in terms of efficiency?

Question

I am in a computer algorithms course where I was faced with a problem to determine the big theta efficiency of $n\log(n) + n^2\log(n)$. The solution is $\Theta(n\log(n))$.

Why was this chosen over $n^2 \log(n)$?

Answer 1

Note that $n \log(n)+n^2 \log(n) = (n+n^2)\log(n)$, which is in $\Theta(f(n)\log(n))$ if and only if $n+n^2\in\Theta(f(n))$. It is obvious that $n+n^2$ can't have a linear asymptotic upper bound, so $f(n)=n^2$ is the better candidate. And indeed $$ 1\,n^2 \le n+n^2 \le 2\,n^2 \quad\text{for $n\ge 1$}. $$ So $n+n^2\in\Theta(n^2)$ and hence $n\log(n)+n^2\log(n)\in\Theta(n^2\log(n))$.

Answer 2

Assume, for simplicity, that $f, g \ge 0$. Remember that we say that $f$ is $\Theta (g)$ if there exist $M, N > 0$ and $n_0 \in \Bbb N$ such that $M g(n) \le f (n) \le N g(n)$ for all $n \ge n_0$. In particular, if $\lim \limits _{n \to \infty} \dfrac f g$ exists, the above definition simplifies to $M \le \lim \dfrac f g \le N$, i.e. $\lim \limits _{n \to \infty} \dfrac f g$ should be in $(0, \infty)$.

But $\lim \limits _{n \to \infty} \dfrac {n \log n + n^2 \log n} {n \log n} = \lim \limits _{n \to \infty} (1 + n) = \infty$, clearly not in $(0, \infty)$, so $n \log n + n^2 \log n$ cannot be $\Theta (n \log n)$ as claimed.

On the other hand, $\lim \limits _{n \to \infty} \dfrac {n \log n + n^2 \log n} {n^2 \log n} = \lim \limits _{n \to \infty} \left( \dfrac 1 n + 1 \right) = 1$, clearly in $(0, \infty)$, so $n \log n + n^2 \log n$ is $\Theta (n^2 \log n)$, confirming your intuition.

Answer 3

Following everyone's analysis, here is an example where you can confirm their answers

Hope this helps!