# Prove that if f ∉ ω(g) →f∈O(g)

I am trying to prove the statement in the title. I have a hard time proving it is true. The way I go about it is by using the definition of $\omega$:

$c\times g(n) < f(n)$; So that if $f \notin \omega(g)$, then $\mathrm{NOT} (c\times g(n)<f(n))$ means that $c\times g(n) \geq f(n)$. And that by definition is Big-Oh.

Is this a correct way of proving the statement in the title?

Thanks, Lukasz

Remarks:

The definition of $\omega$ is that $f(n)$: for all constants $c > 0$, there exists a constant $n_0>0$ ...

So, the negation of that would be: There exists $c\times g(n) \geq f(n)$, correct? Can you think of an example that would disprove the statement?

I think I understand what you are saying. Since the definition states that "for all $c>0$, there exists a constant $n$ ..." The negation of that is: "There exists a constant $c>0$, for which this is not true..."

However, for any $c>0$ there is a constant $n$ big enough that will make the statement true. Am I wrong?

• Welcome to CS.SE! What makes you think the statement is true? (I don't think it is.)
– D.W.
Commented Sep 19, 2016 at 5:21
• $c$ is existentially quantified and $n$ universally. So be careful with that. The negation of an exists (forall), it's not the existential (universal) of the negation. I also strongly suspect it's not true
– Euge
Commented Sep 19, 2016 at 5:47

The claim is not true (unless you add some "nice" conditions on the functions).

Take, for example, the functions $g(n)=n$, and consider the following function $f$: on the even numbers, we'll take $f(n)=n^2$, and on the odd numbers, take $f(n)=n$.

Since $n\notin \omega(n)$, then the assumption holds (that is, $f(n)\notin \omega(g(n))$), but since since $n^2\notin O(n)$, we also have that $f(n)\notin O(g(n))$.

• @DavidRicherby - I agree that it's not clear, but I was thinking more along the lines of monotonicity, rather than continuity (since we're talking about functions from ${\mathbb{N}}$). But I think that there can be a monotonous counterexample as well (but I don't have a concrete one in mind). Commented Sep 19, 2016 at 8:22
• "Monotone", btw. "Monotonous" means boring. :-) Commented Sep 19, 2016 at 8:38
• And the problem is that we definitely want to be able to deal with non-monotone functions. There's no reason that the running time of an algorithm should be monotone. For example, an algorithm for detecting perfect matchings in graphs might sensibly be optimized to immediately return false if there are an odd number of vertices, giving very similar behaviour to your example (linear time on odd inputs and, er, more than that on even ones). Commented Sep 19, 2016 at 8:40
• Well, I definitely think there are monotonous examples :) Regarding the assumption - in many textbooks, the definition of the runtime of a TM is measured w.r.t. all inputs up to size n, in which case the runtime is always non-decreasing, so it can be of interest, especially if the aim of the answer is didactic. Commented Sep 19, 2016 at 8:48
• @Bakuriu - see the example David Richerby gave above, for a non-monotone runtime. As for being Turing computable - this is a very weak requirement, and would obviously not suffice for the claim of the OP to be true (the functions in my answer are Turing computable). Conversely, you might want to study non-computable functions as well (depending on the context). Commented Sep 19, 2016 at 12:24

The key to understand why that statement is false (without conditions on f and g) is to think that if $g$ is not a lower bound for $f$, it does not mean is an upper bound. It could be the case that neither $f$ is a bound for $g$, nor $g$ is a bound for $f$. An example for this is a function $f$ that is, informally, half in $O(g)$ (for even values) and half in $\omega(g)$ (for odd values), so $f$ is neither $O(g)$ nor $\omega(g)$. Details left to you.

Anyway, let's follow the definition and try not to mess things up with the existentials and universals.

$f \in \omega(g) \iff \forall c > 0.\ \exists n_0.\ \forall n ≥ n_0.\ cg(n) < f(n) \quad$

On the other hand,

$f \in O(g) \iff \exists c > 0.\ \exists n_0.\ \forall n ≥ n_0. f(n) ≤ cg(n) \quad$

So if we have that $f \notin \omega(g)$ then

$f \notin \omega(g) \iff \exists c > 0.\ \forall n_0.\ \exists n > n_0.\ \neg (cg(n) < f(n)) \iff$

$\hspace{15.5ex} \exists c > 0.\ \forall n_0.\ \exists n > n_0.\ f(n) \leq cg(n)$

In conclusion, applying the negation to the definition you get something which is not what you need. We manage to get a $c$, and maybe we can pick a $n_0$ as being the minimum one, but we cannot guarantee that the inequality will hold forall $n$s as required.

So, this is not a proof, to proove the statement wrong you need to show that the counter example really works, but maybe this can help you too see why, and how to work with this kind of definitions.