0
$\begingroup$

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

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

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

Then you have:

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

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