2
$\begingroup$

For two any functions $f(n)$ and $g(n)$ always holds:

$f(n) = O(g(n))$ or $g(n) = O(f(n))$

Right?

Thanks

  • 0
    It is false even if you assume $f$ and $g$ are monotonic. On the other hand, there is a special class of functions, called exp-log functions, which can be ordered linearly with big O.2012-05-09

1 Answers 1

4

That's not right. Let $f(x)=\cos x$ and $g(x)=\sin x$.

If $f(x)=O(g(x))$, then there would be some constant $C>0$ so that for $x$ sufficiently large, we would have $\tag{1} |f(x)|\le C|g(x)|. $

But for any positive integer $n$, we have $f(2n\pi)=1$ and $g(2n\pi)=0$. Since we can make $2n\pi$ arbitrarily large, this shows that $(1)$ cannot hold.

I'll leave it to you to show that $g(x)\ne O(f(x))$.

  • 0
    yes, you're right, I got confused.2012-05-10