Finding the Big-O of a function

Question

I have a function here that I need to heuristically find the Big-O of.

n + 4$n^2$$\log(n)$

Would the Big-O of this function be O($n^2$) seeing as how it's the highest order term there or do I have to also consider the logarithm it is being multiplied by?

Answer 1

$u_n=n+4n^2\log(n)$

Note that : $u_n=o(v_n)\implies u_n=\mathcal{O}(v_n) \tag1$

$u_n=o(v_n)\iff \displaystyle \lim_{n\to +\infty} \dfrac{|u_n|}{|v_n|}=0$

So $\displaystyle \lim_{n\to +\infty} \dfrac{n+4n^2\log(n)}{n^p}=0$ if $p>2$

Then $u_n=o(n^p)$ and (1) guarantees that $u_n=\mathcal{O}(n^p)$ with $p>2$

Answer 2

No. $f(n)=O(g(n)$ means $\biggl|\dfrac{f(n)}{g(n)}\biggr| $ is bounded if $n$ is large enough, so $$4n^2\log n=O(n^2\log n),\enspace\textit{a fortiori}\quad n^2\log n=O(n^{2+\varepsilon})\enspace\forall\varepsilon>0. $$

Answer 3

There is a frequent misconception about the uniqueness of the Big-O notation: there is no the Big-O of a function, but as many as you want. In particular, a function is alway a Big-O of itself, and so are all upper bounds (to a constant factor), and all bounds with extra terms with a slower growth.

$$n+4n^2\log n=O(n+4n^2\log n)$$

$$n+4n^2\log n=O(n^2\log n+e^n)$$

$$n+4n^2\log n=O(n^{5/2})$$

$$n+4n^2\log n=O(12000\log n + n\cos n+0.4n^2\log n+\log\log n)$$

$$\cdots$$

---

For a less artificial example, one can say that the number of comparisons performed in Heapsort in the worst case is

$$O(n\log n)$$

but also

$$O(\log n!)$$

and no expression is "better" than the other.

---

This said

$$n+4n^2\log n=O(n^2)$$ does not hold because the ratio is $\dfrac1n+\log n$, which is not bounded by a constant.