0
$\begingroup$

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$.

Can somebody please help me understand what step I'm missing from this proof?

$\endgroup$

3 Answers 3

0
$\begingroup$

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

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

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<c$ 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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – OldCrow
    Commented Dec 9, 2022 at 18:49
0
$\begingroup$

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

Number line

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&<c\\ \therefore f(n)&<2c\cdot g(n) \end{aligned} $$ 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)}&<c/2\\ \therefore (c/2)g(n)&<f(n) \end{aligned} $$ 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.

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

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).

$\endgroup$

Your Answer

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

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