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) &lt; f(n)$; So that if $f \notin \omega(g)$, then $\mathrm{NOT} (c\times g(n)&lt;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 &gt; 0$, there exists a constant $n_0&gt;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&gt;0$, there exists a constant $n$ ..." The negation of that is: "There exists a constant $c&gt;0$, for which this is not true..."

However, for any $c&gt;0$ there is a constant $n$ big enough that will make the statement true. Am I wrong?
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))$.