# Help understanding the proof of the definition of Big-Theta based on limits

I was reading Kleinberg's and Tardo's book (especifically, this one) and, on page 38, these authors define the Big-Theta notation the following way:

Let $$f$$ and $$g$$ be two functions that $$\lim_{n\to\infty}f(n)/g(n)$$ exists and is equal to some number $$c>0$$. Then $$f=\Theta(g)$$.

Then, they provide a proof that connects the classic defition based on sets of functions to this definition based on the limit of the ratio of two functions. This proof goes as:

We will use the fact that the limit exists and is positive to show that $$f=O(g)$$ and $$f=\Omega(g)$$, as required by the definition of $$\Theta(\cdot)$$. Since $$\lim_{n\to\infty}f(n)/g(n)=c>0$$, it follows from the definition of a limit that there is some $$n_0$$ beyond which the ratio is always between $$c/2$$ and $$2c$$. Thus, $$f(n)\leq 2cg(n)$$ for all $$n\geq n_0$$, which implies that $$f=O(g)$$; and $$f\geq c/2\cdot g(n)$$ for all $$n\geq n_0$$, which implies $$f=\Omega(g)$$. $$\blacksquare$$

However, I'm struggling to follow this proof; in particular, I fail to see how or why the authors chose the constants $$c/2$$ and $$2c$$ "from the definition of the limit" (as they say). I consulted Leithold's book on calculus (this one) and, on page 250, I found the following definition for infinite limits (translation is mine):

Let $$f$$ be a function defined for all numbers within some open interval $$(a,\infty)$$. The limit of $$f(x)$$ when $$x$$ grows indefinitely is $$L$$, which is denoted as $$\lim_{x\to\infty}{f(x)}=L$$, if, for any $$\varepsilon >0$$ (no matter how small this number is), there exists a number $$n>0$$ such that: if $$x>n$$, then $$|f(x)-L|<\varepsilon$$.

Applying this definition to Kleinberg's and Tardo's proof, I understand that $$\lim_{n\to\infty}f(n)/g(n)=c$$ implies that, no matter what $$\varepsilon$$ I choose, there's always an $$n_0$$ beyond which $$|f(n)/g(n)-c|<\varepsilon$$ (in other words, the ratio $$f(n)/g(n)$$ differs from $$c$$ within any given margin $$\varepsilon$$). But then, I fail to see how this fact implies that "the ratio is always between $$c/2$$ and $$2c$$", as Kleinberg and Tardos claimed.

I think that the definition of infinite limits allows us to choose (at least in this particular case) any $$\varepsilon$$ that we find convenient, since $$n_0$$ will always exist no matter what we choose. Following this idea, I would suspect that Kleinberg and Tardos simply chose a value for $$\varepsilon$$ for which $$|f(n)/g(n)-c|<\varepsilon$$ would imply that $$c/2\leq f(n)/g(n)\leq 2c$$ is always true. However, I don't think such $$\varepsilon$$ can be chosen under these circumstances, since the distance from $$c/2$$ to $$c$$ is not the same as the distance from $$c$$ to $$2c$$.

By the definition of the limit, for any $$\epsilon$$ we can always establish

$$c-\epsilon<\frac{f(n)}{g(n)}

by choosing $$n$$ sufficiently large.

In fact, the proof stops here, as this reads

$$c_0 g(n)\le f(n)\le c_1 g(n).$$

The author preferred to work with $$\epsilon=\dfrac c2$$ on the left and $$\epsilon=c$$ on the right (this is more "constructive"), but that does not make a big difference.

Technical note: $$c_0$$ must be positive, so we must choose $$\epsilon on the left (hence the $$\frac12$$). There is no such constraint on the right, but the author might as well have kept the same $$\epsilon$$ for clarity.

The reciprocal is not true. As a counter-example, consider

$$f(n)=(2+\sin n)n.$$

We do have

$$n\le (2+\sin n)n\le 3n\implies f(n)=\Theta(n)$$ but the limit does not exist.

• Ah, I think I get it now. The authors chose two different values for $\varepsilon$ instead of just one. Sometimes I just forget about the most basic stuff, many thanks. Also, thank you for mentioning that the converse is not true, that's a good reference for future readers. Commented Dec 9, 2022 at 18:49

I'd like to add a few observations about Yves Daoust's answer. The relation $$(1)\qquad c-\varepsilon<\dfrac{f(n)}{g(n)} can be esaily inferred by tracing $$|f(n)/g(n)-c|<\varepsilon$$ on the number line like so:

That is, $$f(n)/g(n)$$ can be any value in the interval $$(c-\varepsilon,c+\varepsilon)$$. From there, as just explained in my question, we can choose a value for $$\varepsilon$$ that we find convenient.

My confusion was that the authors chose two different values for $$\varepsilon$$. This can be more esily seen by separating the relation (1) in two relations and working separately on them (this was explained by Yves Daoust in his/her answer), as so: $$(2) \qquad\dfrac{f(n)}{g(n)}-c<\varepsilon\\ (3) \qquad c-\dfrac{f(n)}{g(n)}<\varepsilon$$

For (2), we can choose $$\varepsilon=c$$ and get the following: \begin{aligned} \dfrac{f(n)}{g(n)}-c& which satisfies the definition for $$f=O(g)$$ (remember that, no matter what value for $$\varepsilon$$ we choose, there always exists an $$n_0$$ for which $$f(n)<2c\cdot g(n)$$ is true for all $$n\geq n_0$$; this is by the definition of the limit that I stated in my question).

Finally, for (3), we can choose $$\varepsilon=c/2$$ and get the following: \begin{aligned} c-\dfrac{f(n)}{g(n)}& which satisfies the definition for $$f=\Omega(g)$$. Thus, since $$f=O(g)$$ and $$f=\Omega(g)$$, we conclude that $$f=\Theta(g)$$, finishing the proof.

• Slight fix: every inequality has its own $n_0$. The claim holds when you take the maximum of the two.
– user16034
Commented Dec 12, 2022 at 8:44

If the limit exists then f/g will be between c-eps and c+eps for every eps > 0 if n is large enough. The author chose eps=1/2 which is more than good enough to prove big-theta.

But big theta doesn’t require a limit. 2 + cos(n) is big-theta(1).