4
$\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?

$\endgroup$
2
  • 1
    $\begingroup$ Your problem is with mathematical rigour. The definition of big oh you state is not complete. It is that "there exists" a positive constant" $c$ with that property "for sufficiently large n". $\endgroup$
    – fretty
    Oct 14, 2012 at 12:32
  • $\begingroup$ Also, there should be a definition with $\iff$. $\endgroup$
    – Raphael
    Oct 14, 2012 at 16:38

1 Answer 1

8
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .