# Big O notation: relation between Omega and Big O?

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

-

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.

-
I've up-voted this, but just writing $$g(n) \le c \cdot f(n) \Leftrightarrow f(n) \ge \frac{1}{c} \cdot g(n)$$ crudely does the trick and is a lot less complicated (I don't know why you did all that acrobatics with rearranging the inequalities when just dividing both sides by $c$ is sufficient). – Clive Newstead Feb 18 '13 at 20:03
Yeah, that's correct and more easyier. But I'm not so familiar with that kinds of prooves and I'm happy that I made it! So sorry for my acrobatics! Your solution is nice :-) – mythbu Feb 19 '13 at 6:23