# For $f(n) = \log n$ and $g(n) = n^c$, where $0 < c < 1$, is it always true that $f$ is $O(g)$?

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.

• Please check your problem statement. What are $x$, $n$, and $f(3)$? Aug 31, 2013 at 11:15
• ^ Those were typos, it's fixed now. n is the only variable in the functions. Aug 31, 2013 at 11:50

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.
• The first sentence is wrong. Note that $\cos(n)=O(1)$ while $(\cos(n))$ diverges.
• @Did Well this is awkward. Nice counterexample. Apparently my professor lied to me this whole time. It seems that in terms of applying the definition in a practical context, most algorithms don't involve trig functions or negative functions, so we end up replacing the $\limsup$ with $\lim$ and dropping the absolute values anyways. The $\limsup$ definition is certainly more general though. Aug 31, 2013 at 19:58
Let $y=e^{x/c}$. Then $\log y = x/c$ and $y^c=e^{x}$. Since $y$ is a monotonically increasing function of $x$, the problem reduces to showing that every linear function is $O(e^x)$.