0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ You took $c=2$, but then forgot about it? $\endgroup$ – chi Oct 29 '18 at 14:08
  • 1
    $\begingroup$ 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$. $\endgroup$ – Eugen Oct 30 '18 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.