Given $f \in \Omega(g)$, prove that $\mathcal{O}(g) \subseteq \mathcal{O}(f)$

58 Views Asked by At

My proof goes like this:

By definition

$f \in \{ g:\mathbb{N} \rightarrow \mathbb{R}|\exists \beta > 0 \exists n_0 \in \mathbb{N} \forall n \geq n_0 : 0 \leq f(n) \leq \beta g(n) \}$

therefore $0 \leq \beta_f g(n) \leq f(n) \,\forall n \geq n_f$ .

Let $h \in \mathcal{O}(g):=\{f:\mathbb{N} \rightarrow \mathbb{R}|\exists \alpha > 0 \exists n_0 \in \mathbb{N} \forall n \geq n_0 : 0 \leq f(n) \leq \alpha g(n)\}$

and therefore $0 \leq h(n) \leq \alpha_h g(n)\,\forall n \geq n_h$.

Rearrange the inequality to $\frac{h(n)}{\alpha_h} \leq g(n)$.

Substitute g(n) into $0 \leq \beta_f g(n) \leq f(n) \,\forall n \geq n_f$.

Resulting to $0 \leq \frac{\beta_f}{\alpha_h} h(n) \leq f(n) \,\forall n \geq max \{ n_{h}, n_{f}\}$

Rearrange inequality: $0 \leq h(n) \leq \frac{\alpha_h}{\beta_f} f(n)$

This means $h \in \mathcal{O}(f)$ and therefore $\mathcal{O}(g) \subseteq \mathcal{O}(f)$.

Thanks in advance.