# 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 "The Introduction to Algorithms" 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 > 0$$ and $$c > 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 > 0$$ and $$\forall c > 0$$ there exists $$n \geq n_0$$ such that $$f(n) > 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) > 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))$$

• In complexity theory, the big Oh notation is generally used only with integers (even though the definition you are quoting does not state that). – Nathaniel Apr 19 at 11:34

If you consider the following functions defined for $$x\in \mathbb{R}$$:
$$f(x) = \left\{\begin{array}{rl}1 & \text{if }x\in\mathbb{N}\\x&\text{otherwise}\end{array}\right.$$ and $$g(x) = \left\{\begin{array}{rl}x & \text{if }x\in\mathbb{N}\\1&\text{otherwise}\end{array}\right.$$
• neither $$f \in O(g)$$, because whatever the constant $$C$$, $$x\in]C,+\infty[\setminus \mathbb{N}\Rightarrow f(x) > 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) (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$$).