0
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ The first sentence is wrong. Note that $\cos(n)=O(1)$ while $(\cos(n))$ diverges. $\endgroup$
    – Did
    Aug 31, 2013 at 12:04
  • $\begingroup$ @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. $\endgroup$
    – Adriano
    Aug 31, 2013 at 19:58
  • $\begingroup$ "most algorithms don't involve trig functions" Many do not but some do. $\endgroup$
    – Did
    Sep 1, 2013 at 15:33
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .