[Math] Big O notation: relation between Omega and Big O

Question

Can I do this if I need to proove something for $\Omega$: $f(n) \in \Omega(g(n)) \iff g(n) \in O(f(n))$?

Answer 1

Recall the definitions we will need further:

$O(f(n)) = \{g: \mathbb{N} \rightarrow \mathbb{N} ~~|~~ \exists c,n_0 \in \mathbb{N} ~~ \forall n ≥ n_0: g(n) ≤ c ·f(n) \}$

$\Omega(g(n)) = \{f: \mathbb{N} \rightarrow \mathbb{N} ~~|~~ \exists c,n_0 \in \mathbb{N} ~~ \forall n ≥ n_0: f(n) ≥ c·g(n) \}$

We will prove: $f(n) \in \Omega(g(n)) \Leftrightarrow g(n) \in O(f(n))$

Step 1/2: $f(n) \in \Omega(g(n)) \Rightarrow g(n) \in O(f(n))$

$\exists c,n_0 \in \mathbb{N} ~\forall n ≥ n_0: ~ f(n) ≥ c · g(n) \Rightarrow \frac{f(n)}{g(n)} ≥ c \Rightarrow \frac{1}{g(n)} ≥ \frac{c}{f(n)} \Rightarrow g(n) ≤ \frac{1}{c} · f(n) $

And this is exactly the definition of $O(f(n))$.

Step 2/2: $f(n) \in \Omega(g(n)) \Leftarrow g(n) \in O(f(n))$

$\exists c,n_0 \in \mathbb{N}~\forall n ≥ n_0: ~ g(n) ≤ c · f(n) \Rightarrow ... \Rightarrow f(n) ≥ \frac{1}{c} · g(n)$

And this is exactly the definition of $\Omega(f(n))$.

Q.E.D.