Finding the Big-O of a function
Solution 1
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. $$
Solution 2
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.
Related videos on Youtube
Broadsword93
Updated on October 07, 2020Comments
-
Broadsword93 over 2 years
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?
-
Robert Z over 5 yearsYou have to consider the logarithm too.
-
Broadsword93 over 5 years@Robert Z I'm guessing that I have to look it at as a linearithmic notation that takes a higher order than the n?
-
Robert Z over 5 yearsThe function is $O(n^2\log(n))$ or $O(n^c)$ for any $c>2$.
-