2
$\begingroup$

I'm following the Algorithm Design book by Eva Trados. In the 'Basics of Algorithm Analysis' chapter, I've come across a proof that I'm having difficulty understanding and can't find any proper explanation for it.

$$ \lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = c > 0 $$ Given two functions f and g, the proof uses the fact that if a positive limit exists for the limit above, then there is some value $ n_{0} $ beyond which the ratio is always between $\frac{1}{2}c$ and 2c.

What I don't understand is, how do we know that the ratio is between $\frac{1}{2}c$ and 2c ?

$\endgroup$
2
  • $\begingroup$ That is true for any sequence $(a_n)$ with limit $c\gt 0$. $\endgroup$ May 20, 2014 at 0:32
  • $\begingroup$ I am trying to understand the reasoning behind it. Can you direct me to some reading or book that explains this ? $\endgroup$ May 20, 2014 at 0:33

1 Answer 1

2
$\begingroup$

Let $(a_n)$ be any sequence with limit $c\gt 0$. Then by the definition of limit, for any $\epsilon \gt 0$, there is an $N$ such that if $n\gt N$ then $|a_n-c|\lt \epsilon$.

Pick $\epsilon=\frac{c}{2}$. Then there is an $N$ such that if $n\gt N$ we have $|a_n-c|\lt \frac{c}{2}$, or equivalently $$c-\frac{c}{2}\lt a_n \lt c+\frac{c}{2}.$$ From this we can conclude that if $n\gt N$ then $\frac{c}{2}\lt a_n\lt 2c$.

$\endgroup$
6
  • $\begingroup$ Shouldn't c + $\frac{c}{2}$ be $ \frac{3}{2}c $? $\endgroup$ May 20, 2014 at 0:39
  • $\begingroup$ @WasifHyder Then you'd get $\frac c 2 <a_n<\frac3 2 c$. But $\frac 3 2 c<2c$, so what you want follows. $\endgroup$
    – Git Gud
    May 20, 2014 at 0:40
  • $\begingroup$ Ah, okay. Thanks so much! :) Really wish I could upvote this answer. $\endgroup$ May 20, 2014 at 0:40
  • $\begingroup$ Yes, but if $a_n\lt \frac{3}{2}c$ then $a_n\lt 2c$. $\endgroup$ May 20, 2014 at 0:41
  • $\begingroup$ You are welcome. We gave a rather formal answer, but the point is that after a while $a_n$ is very close to $c$. We could have chosen $\epsilon=\frac{c}{10}$, and concluded that there is an $N$ such that if $n\gt N$ then $9c/10\lt a_n\lt 11c/10$. $\endgroup$ May 20, 2014 at 0:44

You must log in to answer this question.

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