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.

This may be a dumb question, but if $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$? I can think of a few counter examples, like $n\in O(n^2)$ and obviously $n^2\notin O(n)$, but one counter example doesn't deny the existence of one case where it is true. Is this true or false? And how can I prove it either way?

Thanks!!

share|improve this question
7  
What if $f(x)=g(x)$? ;) –  N. S. Sep 7 '12 at 2:07
1  
It's hard for me to understand what exactly you want: you already provided a counterexample, thus the question to your post's heading is: NO. Now, there are some cases when it can happen, for example if both functions are constants... –  DonAntonio Sep 7 '12 at 2:07
    
@N.S. How did I not think of that?? Thanks! –  roboguy12 Sep 7 '12 at 2:09
    
@DonAntonio His example shows that the question he asks is sometimes NOT true, his "counter-example" is not a counterexample. It just shows that the implication is not always true, but the question is if it CAN be true? –  N. S. Sep 7 '12 at 2:18
4  
There is in fact a term for such a scenario as $f\in O(g)\wedge g\in O(f)$. We say that $f=\Theta(g)$ (which is an equivalence relation, i.e. it's equivalent to $g=\Theta(f)$). See Wikipedia's table. –  anon Sep 7 '12 at 2:25
add comment

1 Answer

Yes, it's certainly true. We say that $f(n)\in O(g(n))$ if there exists a constant $C_1$ such that $\lvert{f(n)}\rvert < C_1\lvert g(n) \rvert$ for sufficiently large $n$, and similarly $g(n)\in O(f(n))$ if there exists $C_2$ such that $\lvert{g(n)}\rvert < C_2\lvert f(n)\rvert$ for sufficiently large $n$. These both hold if there are constants $A$ and $B$ such that $A\lvert g(n) \rvert < \lvert{f(n)}\rvert < B\lvert g(n) \rvert$ for sufficiently large $n$, or equivalently such that $$ A < \left\lvert{\frac{f(n)}{g(n)}}\right\rvert < B. $$ In this case we say that $f(n)\in\Theta(g(n))$. The relation is symmetric and transitive, and obviously reflexive, so it defines an equivalence relation on the set of functions.

share|improve this answer
add comment

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.