CheckMyProof: Proofs involving Big-O Notation

Question

This is a homework exercise for a few weeks ago and I wanted your feedback on my improved proofs.

For $g: \mathbb{N} \to \mathbb{R}$ let $$o(g):= \{f:\mathbb{N} \to \mathbb{R} |\forall \alpha > 0 : \exists n_0 \in\mathbb{N} : \forall n \geq n_0 : 0 \leq f(n) \leq \alpha g(n)\}$$ Let $g: \mathbb{N} \to \mathbb{R}$ so that $g(n)\not= 0$ for infinitely many $n \in \mathbb{N}$. Prove or disprove

1. $\mathcal{O}(g) \setminus \Theta(g) \subseteq o(g)$
2. $o(g) \subseteq \mathcal{O}(g) \setminus \Theta(g)$
3. $f \in o(g) \implies g \notin o(f)$

Our definitions of $\mathcal{O}$ and $\Omega$ and $\Theta$ are as follows $$ f \in \mathcal{O}(g) \iff \exists n_0 \in \mathbb{N} ~\exists \alpha >0 : 0 \leq f(n) \leq \alpha g(n) ~~\forall n \geq n_0 ~~~\textrm{and} $$ $$ f \in \Omega(g) \iff \exists n_0 \in \mathbb{N} ~\exists \beta >0 : 0 \leq \beta g(n) \leq f(n) ~~\forall n \geq n_0 $$

$$ f \in \Theta(g) \iff f \in \Omega(g) \land f \in \mathcal{O}(g) $$

---

1. The incorrectness of the statement is proven by counterexample.

Let $f(n) := \begin{cases} 1 & n ~\textrm{odd} \\ 0 & n ~\textrm{even} \end{cases}~~~$ and $g(n) = 1$, then $f \in \mathcal{O}(g) \setminus \Theta(g)$ but $f \notin o(g)$.

Proof: From the definition we know, that $$ f \in \mathcal{O}(g) \iff \exists \hat{n_0} \in \mathbb{N} ~\exists \alpha >0 : 0 \leq f(n) \leq \alpha g(n) ~~\forall n \geq \hat{n_0} ~~~\textrm{and} $$ $$ f \notin \Theta(g) \iff \exists \tilde{n_0} \in \mathbb{N} ~\nexists \beta >0 : 0 \leq \beta g(n) \leq f(n) ~~\forall n \geq \tilde{n_0} $$ Combining those statements we obtain for all $ n \geq \tilde{n_0}, \hat{n_0} \in \mathbb{N}$ $$ 0 \leq \beta g(n) \leq f(n) \leq \alpha g(n) \iff 0 < \beta \leq f(n) \leq \alpha $$ Since $~f(n) \in \{0,1\}$, there exists no $\beta >0$ to make $0 < \beta \leq f(n)$ true, because for every even $n$ we obtain $0 = f(n) < \beta ~\forall \beta > 0$. $~~~~\square$

(Question specifically here: $\beta > 0 $, but the condition is $\beta g(n) = \beta \geq 0$. In the last paragraph, do I use $\geq$ or $>$ ?)

---

2. The statement is correct.

Let $f \in o(g)$, then clearly $f \in \mathcal{O}(g)$. Now we have to show that $f \notin \Theta (g)$. Let's assume $f \in \Theta (g)$, while $f \in o(g)$, then follows that $$ f(n) \leq \alpha g(n) ~\forall \alpha > 0 ~\textrm{and}~ n \geq n_0 \in \mathbb{N} \land \beta g(n) \leq f(n) ~\textrm{for one}~ \beta > 0 ~\forall n \geq \tilde{n_0} \in \mathbb{N} $$ Which is a contradiction, because the first condition is only true if $f(n) = \beta g(n)$. Then $\beta g(n) > \alpha \beta g(n)$ for a $\alpha <1$, so the second condition can't hold.

So $f \notin \Theta (g)$ and therefore the statement is true.

---

3. The statement is correct.

Let $f \in o(g)$ and $g \in o(f)$. Then $$ \exists n_0 \in \mathbb{N} ~\forall \alpha > 0: 0 \leq f(n) \leq \alpha g(n) ~~\forall n \geq n_0 ~~~\textrm{and} $$ $$ \exists \tilde{n_0} \in \mathbb{N} ~\forall \tilde{\alpha} > 0: 0 \leq g(n) \leq \tilde{\alpha} f(n) ~~\forall n \geq \tilde{n_0} $$ Combing both conditions we obtain $$ \exists \hat{n_0} := \max\{n_0, \tilde{n_0}\} ~\forall \alpha, \tilde{\alpha} >0 : 0 \leq f(n) \leq \alpha g(n) \leq \alpha \tilde{\alpha} f(n)~~\forall \hat{n_0} \geq n \in \mathbb{N} $$ Which is only possible if $f = g = 0$, but $g \not= 0$ for infinitely many $n \in \mathbb{N}$, producing a contradiction, so we know that $g \notin o(g)$, proving the statement correct.

Alternatively choose $\alpha = 1, \tilde{\alpha} = 0.5$ to obtain $$ 0 \leq f(n) \leq g(n) \leq 0.5 f(n) \implies 2f(n) \leq f(n) \implies 2 \leq 1 $$ arriving at a contradiction. (Here: searching for a better justification of the contradiction)

Answer 1

The proof of the first part has some deviations which should be revised. The proofs of the other parts are essentially correct. The second proof could be reformulated somewhat in order to enhance readability. Nevertheless all the proofs show already a good qualitative approach.

First part: $\mathcal{O}(g) \setminus \Theta(g) \subseteq o(g)$

The choice of the counterexample using $f$ and $g$ is fine. Also showing that $f\in\mathcal{O}(g)$ is correct. The following statement is not correct:

\begin{align*} f \notin \Theta(g) \iff \exists \tilde{n_0} \in \mathbb{N} ~\not\exists \beta >0 : 0 \leq \beta g(n) \leq f(n) ~~\forall n \geq \tilde{n_0} \end{align*} We can instead write for example: \begin{align*} f \notin \Theta(g) &\iff \neg\left(\left(f \in \mathcal{O}(g)\right)\land\left(f \in\Omega(g)\right)\right)\\ &\iff \left(f \not\in \mathcal{O}(g)\right)\lor\left(f \not \in\Omega(g)\right)\\ \end{align*} and since we already know that $f\in\mathcal{O}(g)$ we conclude $f \not\in \Omega(g)$. We obtain according to the definition of $\Omega(g)$: \begin{align*} f \not\in \Omega(g)&\iff\neg\left(\exists \tilde{n}_0 \in \mathbb{N}\, \exists \beta >0\,\forall n \geq \tilde{n}_0 : 0 \leq \beta g(n) \leq f(n) \right)\\ &\iff \forall\tilde{n}_0 \in \mathbb{N}\, \forall\beta >0\,\exists n \geq \tilde{n}_0:\beta g(n)>f(n)\tag{1} \end{align*} The statement (1) is true, since we can take for each $\tilde{n}_0\in\mathbb{N}$ and each $\beta>0$ the value $n=2\tilde{n}_0$ and have $$\beta g(2\tilde{n}_0)=\beta>0=f(2\tilde{n}_0)$$ showing $f \not\in \Omega(g)$.

We conclude $f\in\mathcal{O}(g)\setminus\Omega(g)$.

Let's make a closer look at:

• Since $f(n) \in \{0,1\}$, there exists no $\beta >0$ to make $0 < \beta \leq f(n)$ true, because for every even $n$ we obtain $0 = f(n) < \beta ~\forall \beta > 0$.

The goal of this paragraph is not clearly stated. It seems this is the part showing that $f\not \in o(g)$. But the argument is not sound.

The formulation should be improved since it's not $f(n)\in\{0,1\}$ which is the essence, but the property that $f(n)$ is one for odd $n$. It is also useful to clearly state what it means that $f\not\in o(g)$.

For example:

We show $f\not\in o(g)$. This means according to the definition of $o(g)$: \begin{align*} f\not \in o(g)&\iff \neg\left(\forall \alpha > 0 \, \exists n_0 \in\mathbb{N} \, \forall n \geq n_0 : 0 \leq f(n) \leq \alpha g(n)\right)\\ &\iff \exists\alpha>0\,\forall n_0\in\mathbb{N}\,\exists n\geq n_0: f(n)>\alpha g(n) \end{align*} We take $\alpha=\frac{1}{2}$ and for given $n_0\in\mathbb{N}$ we take $n=2n_0+1$: from which \begin{align*} f(n)=f(2n_0+1)=1>\frac{1}{2}=\alpha g(n) \end{align*} follows, showing that $f\not\in o(g)$.

Here we also use specific settings for $\alpha$ and $n$ which is easier to follow than the arguments with the not existing $\beta>0$ above.

Second part: $o(g)\subseteq \mathcal{O}(g) \setminus \Theta(g)$

The second part is essentially correct. It could be somewhat more clearly structured to enhance readability.

The statement Let's assume $f\in\Theta(g)$ starts an indirect argument. It might be easier to follow by explicitly stating it and again argue based upon the definition.

For example:

We assume indirectly $f\in\Theta(g)$. Since we already know that $f\in\mathcal{O}(g)$ we have to show $f\in\Omega(g)$. This means per definition \begin{align*} f\in \Omega(g)&\iff\exists n_0\in\mathbb{N}\,\exists\beta>0\,\forall n\geq n_0: 0\leq \beta g(n)\leq f(n)\tag{2} \end{align*} on the other hand since $f\in o(g)$ we know that \begin{align*} f\in o(g)&\iff \forall \alpha>0\, \exists\tilde{n}_0\in\mathbb{N}\,0\leq f(n)\leq \alpha g(n)\tag{3} \end{align*} Since we know from (2) there is a $\beta>0$ fulfilling (2) we can take in (3) $\alpha=\frac{\beta}{2}$ which implies \begin{align*} 0\leq f(n)\leq \frac{\beta}{2} g(n)\leq\frac{1}{2} f(n)\qquad\forall n\geq \max\{n_0,\tilde{n}_0\} \end{align*} This implies $f\equiv 0\equiv g$ for all $n\geq \max\{n_0,\tilde{n}_0\}$ showing the contradiction since per definition $g(n)\not =0$ for infinitely many $n$, which proofs the claim.

Third part: $f \in o(g) \implies g \notin o(f)$

The proof is correct. From my point of view explicit settings of variables for $\alpha ,\tilde{\alpha}$ enhances readability. The last paragraph could be formulated

We choose $\alpha = 1, \tilde{\alpha} = 0.5$ to obtain $$ 0 \leq f(n) \leq g(n) \leq 0.5 f(n) $$ arriving at a contradiction for $n$ with $f(n)\neq 0$. This is the case for infinitely $n\in\mathbb{N}$ according to the definition of $g$.