Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

Right?

Thanks

share|improve this question
    
$\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
1  
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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
    
yes, you're right, I got confused. –  Peter May 10 '12 at 10:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.