<p>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.</p>

<hr>

<p>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 <a href="https://en.wikipedia.org/wiki/Hardy_field" rel="nofollow">Hardy field</a>. 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 <a href="https://en.wikipedia.org/wiki/O-minimal_structure" rel="nofollow">o-minimal</a> expansion of the real field for that matter.</p>

CC BY-SA 3.0
2016-09-05T18:49:06.723Z
2016-09-06T08:40:57.610Z
2016-09-06T08:40:57.610Z
Emil Jeřábek
<p>I'm trying to determine under what conditions the following statement is true. </p>

<p>The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$</p>

<p>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".</p>

<p>I can't seem to find it stated outright in any of the books or wikipedia articles.</p>

<p>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).</p>

CC BY-SA 3.0
2016-09-06T07:07:03.820Z
@ClementC., according to [wikipedia](https://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation), Knuth's definition (presumably standard in TCS) is $f = \Omega(g) \iff g = O(f)$. But for the other definition given there ("Hardy-Littlewood"), one can easily come up with counterexamples.
usul
CC BY-SA 3.0
2016-09-06T07:10:51.023Z
@xdavidliu, I'm still not sure what definitions you're using. If you mean what I think you mean by "asymptotically bounded", then $f = O(g) \implies g = \Omega(f)$. I interpret your definition of big-O as "there exists $n_0, C$ such that $f(n) \leq C g(n)$ for all $n \geq n_0$." This implies $g(n) \geq \frac{1}{C} f(n)$ for all $n \geq n_0$, which implies my interpretation of your definition of big-omega.
usul
CC BY-SA 3.0
2016-09-06T10:40:48.280Z
@usul That how I read it -- based on the OP's question, I could not see what the question was to begin with...""asymptotically bounded below (not necessarily tightly) by" seems to refer to the definition of $\Omega$ for which the conclusion trivially holds.
Clement C.
CC BY-SA 3.0
2016-09-07T10:09:55.423Z
@usul The Hardy–Littlewood definition is the *weaker* of the two, it is essentially the infinitely-often version of Knuth’s definition. Thus, the implication still trivially holds for their definition, it’s just no longer an equivalence.
Emil Jeřábek
CC BY-SA 3.0
2016-09-07T15:41:11.903Z
@EmilJeřábek, how about the example in my first comment? Say, $g(n) = 1$ and $f(n) = 1$ if $n$ is odd, $0$ otherwise. It seems to satisfy $f = \Omega(g)$ by the Hardy-Littlewood definition (as infinitely often $f(n) = g(n)$), but not $g = O(f)$ (as infinitely often $g(n) > C f(n)$ for any $C$). Is that right?
usul
CC BY-SA 3.0
2016-09-07T17:14:13.077Z
@usul: but the question goes the other way: $g=O(f) \stackrel{?}{\Rightarrow} f=\Omega(g)$. And this one does certainly hold.
Clement C.
CC BY-SA 3.0
2016-09-05T17:52:44.673Z
What definitions are you using for $O$, $\Theta$, and $\Omega$?
usul
CC BY-SA 3.0
2016-09-05T17:53:12.220Z
For example, what about $f(n) = 0$ if $n$ is odd, else $f(n) = g(n)$?
usul
CC BY-SA 3.0
2016-09-05T18:00:53.770Z
good point, I just edited some points to clarify.
xdavidliu
CC BY-SA 3.0
2016-09-06T01:30:54.837Z
This will look silly, but... what are some examples of these weird functions? And even relaxing the question, are there simple examples of functions $f,g$ such that $f(n)=O(g(n))$ (by itself) does not imply $g(n)=\Omega(f(n))$? (I.e., cases where the second assumption is needed)
Clement C.
<complexity><asymptotics>
obvious property of big O, big Omega, and big Theta
xdavidliu
# obvious property of big O, big Omega, and big Theta

(Asked by: username_0 on 2016-09-05)

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).

**Tags:** complexity, asymptotics

> **Comments:**
> **username_1**: What definitions are you using for $O$, $\Theta$, and $\Omega$?  
> **username_1**: For example, what about $f(n) = 0$ if $n$ is odd, else $f(n) = g(n)$?  
> **username_0**: good point, I just edited some points to clarify.  
> **username_2**: This will look silly, but... what are some examples of these weird functions? And even relaxing the question, are there simple examples of functions $f,g$ such that $f(n)=O(g(n))$ (by itself) does not imply $g(n)=\Omega(f(n))$? (I.e., cases where the second assumption is needed)  
> **username_1**: @ClementC., according to [wikipedia](https://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation), Knuth's definition (presumably standard in TCS) is $f = \Omega(g) \iff g = O(f)$. But for the other definition given there ("Hardy-Littlewood"), one can easily come up with counterexamples.  
> **username_1**: @username_0, I'm still not sure what definitions you're using. If you mean what I think you mean by "asymptotically bounded", then $f = O(g) \implies g = \Omega(f)$. I interpret your definition of big-O as "there exists $n_0, C$ such that $f(n) \leq C g(n)$ for all $n \geq n_0$." This implies $g(n) \geq \frac{1}{C} f(n)$ for all $n \geq n_0$, which implies my interpretation of your definition of big-omega.  
> **username_2**: @username_1 That how I read it -- based on the OP's question, I could not see what the question was to begin with...""asymptotically bounded below (not necessarily tightly) by" seems to refer to the definition of $\Omega$ for which the conclusion trivially holds.  
> **username_3**: @username_1 The Hardy–Littlewood definition is the *weaker* of the two, it is essentially the infinitely-often version of Knuth’s definition. Thus, the implication still trivially holds for their definition, it’s just no longer an equivalence.  
> **username_1**: @EmilJeřábek, how about the example in my first comment? Say, $g(n) = 1$ and $f(n) = 1$ if $n$ is odd, $0$ otherwise. It seems to satisfy $f = \Omega(g)$ by the Hardy-Littlewood definition (as infinitely often $f(n) = g(n)$), but not $g = O(f)$ (as infinitely often $g(n) > C f(n)$ for any $C$). Is that right?  
> **username_2**: @username_1: but the question goes the other way: $g=O(f) \stackrel{?}{\Rightarrow} f=\Omega(g)$. And this one does certainly hold.  

---

## 1 answers

### Answer by username_3 on 2016-09-05. Score: 6 | Accepted answer

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/O-minimal_structure) expansion of the real field for that matter.


---

