Need to prove $n^2 + 10n \log_2 n = O(n^2 )$ for big $O$ notation

Question

I need to prove this. I am not sure how to go about it. I know you need to prove something like $n_0$ such that $\log_2 n \leq n$, for all $n \geq n_0$

Answer 1

Yes, you need to find $n_0$ such that $10\log_2 n \leq n$ (note the $10$ that you forgot) for all $n \geq n_0$.

Finding an $n_0$ for which the inequality holds is easy: try a large enough value, say $n_0 = 100$ and you'll see it works.

Next you need to prove that the inequality holds for all $n \geq n_0$. For that, you can compute the derivative of $n - 10 \log_2 n$ (pretending $n$ is a real-valued variable) and show that it is always positive for $n \geq n_0$.

Answer 2

You need to prove that $\exists c>0$ such that for all $n>n_0$, it holds that $n^2+10n\log_2 n<cn^2$. Remark that $\log_2 n<n$ for $n>1$ and hence we can write:

$$ n^2+10n\log_2 n<n^2+10n^2<cn^2 $$

which hold true for $c>11$ and for $n>2$. Hence, you may choose $n_0=2$.