Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ Before you downvote, please note that this question is distinct from this similar looking question
I came across the following the problem in &quot;The Introduction to Algorithms&quot; by Cormen et. al.
Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically non negative, either $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ or both.
In this book, $\overset{\infty}{\Omega}(g(n))$ is defined as follows:
$f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq cg(n) \geq 0$ for infinitely many integers $n$. Please note that here it says integers.
Proof from a solution manual
One approach is to show that if $f(n) \neq O(g(n))$ then $f(n) = \overset{\infty}{\Omega}(g(n))$.
In the book big Oh is defined as follows:
$f(n) = O(g(n))$ if there exists $n_0 &gt; 0$ and $c &gt; 0$, such that $\forall n \geq n_0$, $0 \leq f(n) \leq cg(n)$. Please note these inequalities are valid not just for integer $n$'s but for all $n \geq n_0$.
$f(n) \neq O(g(n)) \implies $ $\forall n_0 &gt; 0$ and $\forall c &gt; 0$ there exists $n \geq n_0$ such that $f(n) &gt; cg(n)$
I am not going into the details but, by choosing different values for $n_0$ we can show that there are infinitely many real $n$ such that $f(n) &gt; cg(n)$. However to prove that $f(n) = \overset{\infty}{\Omega}(g(n))$ we need to show that these infinitely many $n$'s are integers.
My question is could you please show that there are infinitely many integers not just real numbers, that satisfy $f(n) \geq g(n) \geq 0$ when $f(n) \neq O(g(n))$
If you consider the following functions defined for $x\in \mathbb{R}$:
$f(x) = \left\{\begin{array}{rl}1 &amp; \text{if }x\in\mathbb{N}\\x&amp;\text{otherwise}\end{array}\right.$ and $g(x) = \left\{\begin{array}{rl}x &amp; \text{if }x\in\mathbb{N}\\1&amp;\text{otherwise}\end{array}\right.$
Then you have:

neither $f \in O(g)$, because whatever the constant $C$, $x\in]C,+\infty[\setminus \mathbb{N}\Rightarrow f(x)  &gt; Cg(x)$;
nor $f\in \overset{\infty}{\Omega}(g)$ because whatever the constant $C$, $n\in]\frac{1}{C},+\infty[\cap\mathbb{N}\Rightarrow f(n)&lt;Cg(n)$ (so there cannot be infinitely many integers so that $f(x) \geq Cg(n)$).

So the question here implicitly supposes that the big Oh notation considers that $n\in\mathbb{N}$ (and I think that's why the chosen notation is $n$).