2
$\begingroup$

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?

Note to the comments:

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?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What makes you think the statement is true? (I don't think it is.) $\endgroup$ – D.W. Sep 19 '16 at 5:21
  • $\begingroup$ $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 $\endgroup$ – Euge Sep 19 '16 at 5:47
9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @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). $\endgroup$ – Shaull Sep 19 '16 at 8:22
  • 1
    $\begingroup$ "Monotone", btw. "Monotonous" means boring. :-) $\endgroup$ – David Richerby Sep 19 '16 at 8:38
  • 1
    $\begingroup$ 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). $\endgroup$ – David Richerby Sep 19 '16 at 8:40
  • 3
    $\begingroup$ 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. $\endgroup$ – Shaull Sep 19 '16 at 8:48
  • 1
    $\begingroup$ @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). $\endgroup$ – Shaull Sep 19 '16 at 12:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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