# Understanding big O notation for exponent functions

I have been trying to understand big O notation for log functions. Consider the following two functions: $$f(x) = log_2x$$ $$g(x) = log_3x$$

Now, with a little bit of research that I did, I realized that
$$f(x)∈O(g(x))$$ $$g(x)∈O(f(x))$$

because the same logs with different bases differ from each other by a constant and hence the above two points make sense.

Now I am trying to understand the behavior of the following two functions: $$f(x)= n^5$$ $$g(x)= 5^n$$

Can someone help me reason as to how do I go about understanding the big O notation for these two functions like I did for the log function

• $g$ grows much faster than $f$ in the second example (specifically, $\frac{g(n)}{f(n)} \to \infty$ as $n \to \infty$). – angryavian Sep 8 '20 at 4:14
• If youre just trying to compare the two you need to do a little analysis. Youll see one of the derivatives is much greater than the other for large n. – Algebraic Sep 8 '20 at 4:16
• since g grows much faster than f, is it g(x)∈O(f(x)) or the other way around..i guess I really don't know what ∈ means ? – Amistad Sep 8 '20 at 4:17
• @Algebraic..how would I do that ? – Amistad Sep 8 '20 at 4:17
• Read the definition of big O carefully. $f(n) \in O(g(n))$ means $f(n)$ is bounded above by a constant times $g(n)$, so $g$ can grow much faster than $f$, but $f$ cannot grow faster than $g$. – Ross Millikan Sep 8 '20 at 4:19

## 2 Answers

A crucial point is that anything (greater than $$1$$) to the $$n$$ power grows much faster (eventually) than any power of $$n$$. In your example, then $$f(n) \in O(g(n))\\ g(n) \not \in O(f(n))$$ This is still true if $$f(n)=n^{1000000}, g(n)=1.0000001^n$$ but it takes longer for the eventual domination to set in.

$$f(x) \in O(g(x))$$ if $$|f(x)| < C|g(x)|$$ for large enough $$x$$, for some $$C$$.

Note that the function $$h(x)=x^{1/x}$$ has positive derivative for $$x\in (0,e)$$ and negative derivative for $$x\in (e,\infty)$$, so you have for large $$n$$, (for any $$n\gt 5$$) $$n^{1/n} \lt 5^{1/5} \implies n^5 \lt 5^n$$ which settles the fact that $$f(x)\in O(g(x))$$ in your example.

However, with $$C=5^{1/5}$$, \begin{aligned}\dfrac{g(n)}{f(n)}=\dfrac{5^n}{n^5}=\left(\dfrac{5^{1/5}}{n^{1/n}}\right)^{5n}=\lambda \implies \ln\lambda&=5n\ln C-5n\ln(n^{1/n})\\ &=5C'n-\dfrac{5n}{n}\ln n\\ &=5C'n-5\ln n \\\implies \ln\lambda&= 5n\left(C'-\dfrac{\ln n}{\ln(n+1)}\dfrac{\ln(n+1)}{n}\right) \end{aligned} Now as $$n\to\infty$$ the term in the brackets has a finite limit but
$$5n\to\infty\implies \ln \lambda \to \infty \stackrel{n\to\infty}{\implies} \dfrac{g(n)}{f(n)}=\lambda \to \infty$$, as mentioned in the first comment, which in the language of analysis, means that for any $$M\in \Bbb{R}$$, $$\dfrac{g(n)}{f(n)}>M \ \text{for large enough n}\\ \implies \text{for no M'\in\Bbb{R},} \ g(n)< M'f(n) \implies g(n) \notin O(f(n))$$ You might consider checking out this related answer on StackOverflow.