4

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

roboguy12
  • 581
  • 2
  • 7
  • 18
  • 7
    What if $f(x)=g(x)$? ;) – N. S. Sep 07 '12 at 02: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 07 '12 at 02:07
  • @N.S. How did I not think of that?? Thanks! – roboguy12 Sep 07 '12 at 02: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 07 '12 at 02: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 07 '12 at 02:25

1 Answers1

3

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.

mjqxxxx
  • 41,358