Does lim(f/g) = 0 imply lim(g/f) = ∞?

120 Views Asked by At

I got two functions f,g : N -> R++

The domain is the natural numbers (without 0) and the range is the positive numbers only (without 0)

I know that f(n) = o(g(n)) which means lim n→∞ f(n)/g(n) = 0

I know that small o imply big o, which means f(n) = O(g(n)) which means there's a C>0 and N and for every n>N I get f(n) >= C*g(n)

Also f(n) = O(g(n)) implies g(n)=Ω(f(n)) but I can't quite prove that it's imply lim n→∞ g(n)/f(n) = ∞

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: You want to show $\lim_{n\to\infty}\frac{g(n)}{f(n)}=+\infty$. Spelling out the definitions, this is $$ \forall L\colon\exists N\colon\forall n>N\colon \frac{g(n)}{f(n)}>L.$$ As we are given that $f(n)$, $g(n)$ are positive (and hence so is their quotient), observe that $\frac{g(n)}{f(n)}>L$ is trivially true for $L\le 0$ whereas for $L>0$, the inequality is equivalent to $\frac{f(n)}{g(n)}<\frac1L$. Can you see how the claim now follows from the epsilontical definition of $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$?


Addendum: Can you also see how the claim breaks down if we do not know that $f,g$ are positive?