3
$\begingroup$

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?

  • 0
    Also, there should be a definition with $\iff$.2012-10-14

1 Answers 1

7

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