0
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ What definitions are you using for $O$, $\Theta$, and $\Omega$? $\endgroup$
    – usul
    Sep 5, 2016 at 17:52
  • $\begingroup$ For example, what about $f(n) = 0$ if $n$ is odd, else $f(n) = g(n)$? $\endgroup$
    – usul
    Sep 5, 2016 at 17:53
  • $\begingroup$ good point, I just edited some points to clarify. $\endgroup$
    – xdavidliu
    Sep 5, 2016 at 18:00
  • $\begingroup$ 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) $\endgroup$
    – Clement C.
    Sep 6, 2016 at 1:30
  • 3
    $\begingroup$ @ClementC., according to wikipedia, 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. $\endgroup$
    – usul
    Sep 6, 2016 at 7:07

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.