0
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ $g$ grows much faster than $f$ in the second example (specifically, $\frac{g(n)}{f(n)} \to \infty$ as $n \to \infty$). $\endgroup$ – angryavian Sep 8 '20 at 4:14
  • $\begingroup$ 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. $\endgroup$ – Algebraic Sep 8 '20 at 4:16
  • $\begingroup$ 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 ? $\endgroup$ – Amistad Sep 8 '20 at 4:17
  • $\begingroup$ @Algebraic..how would I do that ? $\endgroup$ – Amistad Sep 8 '20 at 4:17
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Sep 8 '20 at 4:19
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.