I'm trying to determine under what conditions the following statement is true. The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$where $O$ means asymptotically bounded above (not necessarily tightly) by, $\Omega$ means asymptotically bounded below (not necessarily tightly) by and $\Theta$ means asymptotically bounded both above and below.I can't seem to find it stated outright in any of the books or wikipedia articles.I'm sure there are counterexamples where we can construct weird functions to contradict the statement, but I'm wondering whether the statement is true for all ordinary functions we typically encounter (of course, it would be necessary to rigorously define ordinary here).
obvious property of big O, big Omega, and big Theta
complexity;asymptotics
EDIT: Now that I have fresh eyes in the morning, I see that I have thoroughly misread the question. The answer below applies to if $f(n)\ne O(g(n))$, then $f(n)=\Omega(g(n))$. As noted in comments above, the question as actually stated has a trivially true answer for all functions, that is, $f(n)=O(g(n))$ is equivalent to $g(n)=\Omega(f(n))$ immediately from the definition.The answer is positive if $f$ and $g$ belong to a well-behaved family of functions which ensures that they are asymptotically comparable; in particular, if they are (restrictions to $\mathbb N$ of) functions taken from a Hardy field. For example, this holds if both functions are first-order definable (with parameters) in the real exponential field $(\mathbb R,+,\cdot,\exp)$, or in any o-minimal expansion of the real field for that matter.