Big O order of a function

Question

I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working.

My answer is O(n^2) because it's the term with the highest degree. However, I'm not really sure how to show it. Am I right by saying that it has to be proven like this -> f(n) is an element of O(n^2). So far, I've only done questions like n^2 + 2n + 1 and I have to find c and k values. I'm not quite sure how to do this one. Can anyone help me out, please?

Thanks

Answer 1

You need to show that there is an index $n_0\geq 0$ and some $c>0$ such that $f(n) \leq c\cdot n^2$, for all $n\geq n_0$. Here you can take $c=2$.

This leaves you with showing that $n \log_2(n) + log_2(n) \leq n^2$, for high enough values of $n$.

This holds because $\lim_{n\to\infty}\frac{log_2(n)}{n} = 0$.