0
$\begingroup$

Basically what i am trying to prove is this : $f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $

I guess that if we take the definition of $f(n) = Ω (g(n))$ , which means that $f(n) \ge cg(n) $ for every $ n \ge n0$ and then flip the relation so that it becomes $\frac{1}{f(n)} \le \frac{1}{c} \frac{1}{g(n)}$ then we can say that the statement is true , however i am not sure if this is correct or not . Can anyone help me prove it correctly or disprove it ? Thank you .

$\endgroup$
1
  • $\begingroup$ Please don't delete your question after it has been answered. We are trying to build an archive of knowledge, that will be useful not only to the person asking but to others in the future as well. Deleting your question after someone has taken the time to answer it, potentially with this mission in mind, can be considered impolite. $\endgroup$
    – D.W.
    May 2 at 20:26

1 Answer 1

0
$\begingroup$

$$\forall n>n_0:f(n)\ge c\,g(n)>0\implies\frac1{f(n)}\le \frac 1c\frac1{g(n)}$$ is true.

Just a remark: $n_0$ must be taken larger than any root of $f$ and $g$. A pathological counter-example is

$$1=\Omega\left(\sin\left(\frac{n\pi}2\right)\right).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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