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
    $\sin$ and $\cos$2012-05-09
  • 0
    I don't understand you, That affirmation always holds? True or False.2012-05-09
  • 1
    It's false. Let $f(x)=\cos x$ and $g(x)=\sin x$. Neither is big-O of the other.2012-05-09
  • 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
    I might be missing something... But simply setting $C=1$ suffices to show that $\sin x \in O(\cos x)$ and $\cos x \in O(\sin x)$, since both functions are bounded no matter how large $x$ grows. That said, if you look at $f(x) = x \cos x$ and $g(x) = x \sin x$ then your argument holds.2012-05-10
  • 0
    @Peter They are both $O(1)$. But it is not true that $|\cos x|\le |\sin x|$ for all $x$ sufficiently large. I'm using the definition [here](http://en.wikipedia.org/wiki/Big_O_notation) for $f(x)=O(g(x))$ as $x\rightarrow\infty$.2012-05-10
  • 0
    yes, you're right, I got confused.2012-05-10