# Big-O notation always holds for this two functions?

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

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

Right?

Thanks

-
$\sin$ and $\cos$ –  David Mitra May 9 '12 at 22:53
I don't understand you, That affirmation always holds? True or False. –  Albert May 9 '12 at 22:55
It's false. Let $f(x)=\cos x$ and $g(x)=\sin x$. Neither is big-O of the other. –  David Mitra May 9 '12 at 22:56
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. –  sdcvvc May 9 '12 at 23:05

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))$.
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. –  Peter May 10 '12 at 3:08
@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 for $f(x)=O(g(x))$ as $x\rightarrow\infty$. –  David Mitra May 10 '12 at 3:17