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

1 Answer 1

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$
2
  • $\begingroup$ You took $c=2$, but then forgot about it? $\endgroup$
    – chi
    Oct 29, 2018 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, 2018 at 20:50

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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