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?

$\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 '12 at 12:32
  • $\begingroup$ Also, there should be a definition with $\iff$. $\endgroup$ – Raphael Oct 14 '12 at 16:38
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.