0

I am struggling on some problems asking me to prove that one function is Big-Oh of another function, but these functions are a little more complicated than the typical examples seen in practice.

For example, Prove $(\log n)^3 \in O(\sqrt{n})$

I know I need to prove that $(\log n)^3 \leq c*\sqrt{n}$ for all $n > n_0$, but I'm not sure how I would even go about finding some specific values of $c$ and $n_0$?

nickalh
  • 1,263
Matthew Kaplan
  • 105
  • 7
  • 1
    to find c and n, find $any$ intersection point for $(\log n)^3 = c \cdot \sqrt{n}$. I believe c can be a real number, right? In Big O notation, may students are hung up on the precision used for many math classes. Because all three, Big O, Omega and theta are inequalities, there are usually we can often ta

    Example- $n^3 + 10^9 \cdot n^2 \in O(n^4)$ because we can throw away the $10^9 n^2$ term, for sufficiently large n and $n^3 < n^4$ for positive integers.

     – nickalh Jan 26 '24 at 03:24
  • 1
    We use $ or $$ symbols to begin and end mathjax notation, instead of ' symbols. This https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference explains quite a bit about math formatting on M.SE. Let me know if this is not what you meant. – nickalh Jan 26 '24 at 03:29
  • 1
    The catch off the top of my head is proving they never cross after your intersection point. I think A. rephrasing as continuous functions, B. taking the derivative of each side, then C. showing derivative of $\frac{d}{dx}(\log n)^3 \leq \frac{d}{dx} c\cdot \sqrt{n}$ is the common method. – nickalh Jan 26 '24 at 03:34
  • 1
    You can prove (using l'Hôpital's rule, for example) that $\lim_{n\to\infty}\frac{(\log n)^3}{\sqrt{n}}=0<\infty$. This implies $(\log n)^3=O(\sqrt{n})$. (See the table in https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations.) – Gonçalo Jan 26 '24 at 15:13

0 Answers0