4
$\begingroup$

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

  • 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](http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations).2012-09-07

1 Answers 1

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.