# Big O order of a function

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

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$$.
• You took $c=2$, but then forgot about it?
• No, it was just simplified away: $n^2+ n log_2(n) + log_2(n) \leq 2 n^2$ is equivalent with $n log_2(n) + log_2(n) \leq n^2$. Oct 30, 2018 at 20:50