In complexity analysis, basic functions you encounter are functions like $f_1(n) = \log n$, $f_2(n) = n^2$ and $f_3(n) = n^3$. It is fairly obvious to me that $f_1$ is $O(f_2)$ and $O(f_3)$, but it is harder for me to see that $f_1$ is $O(f_4)$, where $f_4(x) = n^c$ and $0 < c < 1$. I can imagine that $f_1$ eventually grows slower than $f_4$, but it's hard for me to substantiate this. If this is the case, can anyone explain it/justify it?
P.S.: Is there any rule that I can invoke in this instance? I know that $f_1$ is always slower than a polynomial, but $f_4$ does not seem like a polynomial, since the exponent is not an integer.
Use the fact that $f(n) = O(g(n))$ iff $\limsup_{n\to\infty}\left|\dfrac{f(n)}{g(n)}\right|=K$, where $K$ is some real constant. Hence, since $c>0$, our limit is of the indeterminate form $\dfrac{\infty}{\infty}$, so we may apply L'Hopital's Rule to obtain: $$ \limsup_{n\to\infty}\left|\dfrac{\log n}{n^c}\right| = \lim_{n\to\infty} \dfrac{\log n}{n^c} = \lim_{n\to\infty} \dfrac{1/n}{cn^{c-1}} = \lim_{n\to\infty} \dfrac{1}{cn^{c}} = 0 \in \Bbb{R} $$ where the last limit worked out since $c>0$. Hence, $\log n = O(n^c)$, as desired.