Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$

Question

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$.

So I know that

$$O(g(n)) \Rightarrow f(n) \leq c\cdot g(n)$$

and that

$$\Omega(g(n)) \Rightarrow f(n) \geq c\cdot g(n)$$

but how do you use these to do the above proof?

Answer 1

I'm not quite sure what definitions you are working with, but for $f, g : \mathbb{N} \to \mathbb{N}$ I'd say $f(n)$ is (or $\in$) $O(g(n))$ if there is a constant $c > 0$ and $N \in \mathbb{N}$ such that $f(n) \leq c\cdot g(n)$ for all $n \geq N$; and similarly for $f(n)$ is $\Omega(g(n))$.

As $f(n)$ is $O(g(n))$ there is a constant $c > 0$ and $N \in \mathbb{N}$ such that

$$f(n) \leq c\cdot g(n)$$

for all $n \geq N$. Rearranging this inequality, we have

$$\frac{1}{c}\cdot f(n) \leq g(n)$$

for all $n \geq N$. Letting $K = \frac{1}{c}$ we can rewrite this inequality as

$$g(n) \geq K\cdot f(n)$$

for all $n \geq N$. As $c > 0$, $K > 0$, this inequality shows that $g(n)$ is $\Omega(f(n))$.