Finding the Big-O of a function

discrete-mathematics logarithms computational-complexity

2,710

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.

2,710

Broadsword93

Updated on October 07, 2020

Comments

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 years
  
  You 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 years
  
  The function is $O(n^2\log(n))$ or $O(n^c)$ for any $c>2$.