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
- $\mathcal{O}(g) \setminus \Theta(g) \subseteq o(g)$
- $o(g) \subseteq \mathcal{O}(g) \setminus \Theta(g)$
- $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) $$
- 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 $>$ ?)
- 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.
- 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)