# If $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$?

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!!

-
What if $f(x)=g(x)$? ;) – N. S. Sep 7 '12 at 2:07
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
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

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.