chap9.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 9 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
% This chapter must begin on right-hand page
% because: (a) it looks good; (b) there's no running head till 3rd page of chapter!
\input gkpmac
\refin bib
\pageno=439
\refin chap2
\refin chap3
\refin chap4
\refin chap5
\refin chap6
\refin chap7

\beginchapter 9 Asymptotics

EXACT ANSWERS are great when we can find them; there's something very
satisfying about complete knowledge. But there's also a time when
approximations are in order. If we run into a sum or a recurrence
whose solution doesn't have a closed form (as far as we can tell), we still
would like to know something about the answer; we don't have to insist
on all or nothing. And even if we do have a closed form, our knowledge
might be imperfect, since we might not know how to compare it with
other closed forms.

For example, there is (apparently) no closed form for the sum
\begindisplay
S_n=\sum_{k=0}^n{3n\choose k}\,.
\enddisplay
But it is nice to know that
\begindisplay
S_n\sim 2{3n\choose n}\,,\qquad\hbox{as $n\to\infty$};
\enddisplay
we say that the sum is ``"asymptotic" to'' $2{3n\choose n}$.
\g Uh oh \dots\ here comes that A-word.\g
It's even nicer to have more detailed information, like
\begindisplay
S_n={3n\choose n}\biggl(2-{4\over n}+O\Bigl({1\over n^2}\Bigr)\biggr)\,,
\eqno\eqref|opening-sum|
\enddisplay
which gives us a ``relative error of order $1/n^2$.'' But even this isn't enough
to tell us how big $S_n$ is, compared with other quantities. Which is larger,
$S_n$ or the Fibonacci number~$F_{4n}$? Answer: We have $S_2=22>F_8=21$ when
$n=2$; \looseness=-1
but $F_{4n}$ is eventually larger, because
$F_{4n}\sim \phi^{4n}\!/\sqrt5$ and $\phi^4\approx6.8541$, while
\begindisplay
S_n=\sqrt{3\over\pi n}(6.75)^n\biggl(1-{151\over72n}+O\Bigl({1\over n^2}\Bigr)
\biggr)\,.
\eqno\eqref|opening-asympt|
\enddisplay
Our goal in this chapter is to learn how to understand and to
derive results like this without great pain.

The word {\it"asymptotic"\/} stems from a Greek root meaning
\g Other words like `symptom' and `ptomaine' also come from this root.\g
``not falling together.\qback'' When ancient Greek mathematicians
studied conic sections, they considered hyperbolas like the graph of
$y=\sqrt{1+x^{\mathstrut2}}$,
\begindisplay
\unitlength=.2in
\beginpicture(10,6)(-5,-1)
\put(-1,-1){\line(1,1)6}
\put(1,-1){\line(-1,1)6}
\put(-5,0){\line(1,0){10}}
\put(0,-1){\line(0,1)6}
\put(0,0){\squine(0,0.41421355,1,1.0,1.0,1.41421357)}
\put(0,0){\squine(1,1.38742588,2,1.41421357,1.68816501,2.23606798)}
\put(0,0){\squine(2,2.4142136,3,2.23606798,2.60655183,3.16227767)}
\put(0,0){\squine(3,3.43405694,4,3.16227767,3.57406026,4.12310565)}
\put(0,0){\squine(4,4.4470902,5,4.12310565,4.55684686,5.0990195)}
\put(0,0){\squine(-0,-0.41421355,-1,1.0,1.0,1.41421357)}
\put(0,0){\squine(-1,-1.38742588,-2,1.41421357,1.68816501,2.23606798)}
\put(0,0){\squine(-2,-2.4142136,-3,2.23606798,2.60655183,3.16227767)}
\put(0,0){\squine(-3,-3.43405694,-4,3.16227767,3.57406026,4.12310565)}
\put(0,0){\squine(-4,-4.4470902,-5,4.12310565,4.55684686,5.0990195)}
\endpicture
\enddisplay
which has the lines $y=x$ and $y=-x$ as ``asymptotes.\qback'' The
curve approaches but never quite touches these asymptotes, when
$x\to\infty$. Nowadays we use ``asymptotic'' in a broader sense to
mean any approximate value that gets closer and closer to the truth,
when some parameter approaches a limiting value. For us, asymptotics
means ``almost falling together.\qback''

Some asymptotic formulas are very difficult to derive, well beyond
the scope of this book. We will content ourselves with an introduction
to the subject; we hope to acquire a suitable foundation on which
further techniques can be built. We will be particularly interested
in understanding the definitions of `$\sim$' and `$O$' and similar
symbols, and we'll study basic ways to manipulate asymptotic quantities.

\beginsection 9.1 A Hierarchy

Functions of $n$ that occur in practice usually have different ``asymptotic
growth ratios''; one of them will approach infinity faster than another.
We formalize this by saying that
\begindisplay
f(n)\prec g(n)\quad\iff\quad\lim_{n\to\infty}{f(n)\over g(n)}\!=\!0\,.
\eqno\eqref|prec-def|
\enddisplay
 This relation is
transitive: If $f(n)\prec g(n)$ and
$g(n)\prec h(n)$ then $f(n)\prec h(n)$.
\g All functions great~and small.\g
We also may write $g(n)\succ f(n)$ if $f(n)\prec g(n)$.
This notation was introduced in 1871 by Paul "du Bois-Reymond"~[|du-bois|].

For example, $n\prec n^2$; informally we say that $n$ grows
more slowly than~$n^2$. In fact,
\begindisplay
n^\alpha\prec n^\beta\iff \alpha<\beta\,,
\eqno\eqref|power-prec|
\enddisplay
when $\alpha$ and $\beta$ are arbitrary real numbers.

There are, of course, many functions of $n$ besides powers of~$n$. We can
use the $\prec$ relation to rank lots of functions into an asymptotic
pecking order that includes entries like this:
\begindisplay
1\prec\log\log n\prec\log n\prec n^\epsilon\prec n^c\prec n^{\log n}
\prec c^n\prec n^n\prec c^{@ c^n}\,.
\enddisplay
(Here $\epsilon$ and $c$ are arbitrary constants with $0<\epsilon<1<c$.)

All functions listed here, except~$1$, go to infinity as $n$ goes
to infinity. Thus when we try to place a new function in this hierarchy,
we're not trying to determine {\it whether\/} it becomes infinite but
rather {\it how fast}.

It helps to cultivate an expansive attitude when we're doing asymptotic
analysis: We should {\sc "think big"}, when imagining a variable that
"!thinking big"
approaches infinity. For example, the hierarchy says that
$\log n\prec n^{0.0001}$; this might seem wrong if we limit our
horizons to teeny-tiny numbers like one googol, $n=10^{100}$. For in
that case, $\log n=100$, while $n^{0.0001}$ is only $10^{0.01}\approx
1.0233$. But if we go up to a googolplex, $n=10^{10^{100}}$, then
$\log n=10^{100}$ pales in comparison with
$n^{0.0001}=10^{10^{96}}$.

Even if $\epsilon$ is extremely small (smaller than, say, $1/10^{10^{100}}$),
the value of~$\log n$ will be much smaller than the value of~$n^\epsilon$,
if $n$~is large enough. For
if we set $n=10^{10^{2k}}$, where $k$~is so large that
$\epsilon\ge10^{-k}$, we have
$\log n=10^{2k}$
but $n^\epsilon\ge 10^{10^k}$. The ratio $(\log n)/n^\epsilon$ therefore
approaches zero as $n\to\infty$.

The hierarchy shown above deals with functions that go to infinity.
Often, however, we're interested in functions that go to zero, so it's
useful to have a similar hierarchy \g A loerarchy?\g
for those functions. We get one by taking reciprocals, because
when $f(n)$ and $g(n)$ are never zero we have
\begindisplay
f(n)\prec g(n)\iff {1\over g(n)}\prec{1\over f(n)}\,.
\eqno
\enddisplay
Thus, for example, the following functions (except $1$) all go to zero:
\begindisplay \nulldelimiterspace=0pt
{1\over c^{@ c^n}}\prec
{1\over n^n}\prec
{1\over c^n}\prec
{1\over n^{\log n}}\prec
{1\over n^c}\prec
{1\over n^\epsilon}\prec
{1\over\log n}\prec
{1\over\log\log n}\prec
1\,.
\enddisplay

Let's look at a few other functions to see where they fit in.
The number $\pi(n)$ of primes less than or equal to~$n$
is known to be approximately $n/\!@\ln n$. Since $1/n^\epsilon\prec
1/\!@\ln n\prec1$, multiplying by~$n$ tells us that
\begindisplay
n^{1-\epsilon}\prec\pi(n)\prec n\,.
\enddisplay
We can in fact generalize \eq(|power-prec|) by noticing, for example, that
\begindisplay
&n^{\alpha_1}(\log n)^{\alpha_2}(\log\log n)^{\alpha_3}\prec
n^{\beta_1}(\log n)^{\beta_2}(\log\log n)^{\beta_3}\cr
&\hskip7em\iff
(\alpha_1,\alpha_2,\alpha_3)<
(\beta_1,\beta_2,\beta_3)\,.
\eqno
\enddisplay
Here `$(\alpha_1,\alpha_2,\alpha_3)<(\beta_1,\beta_2,\beta_3)$' means
"lexicographic order" (dictionary order); in other words, either
$\alpha_1<\beta_1$, or
$\alpha_1=\beta_1$ and $\alpha_2<\beta_2$, or
$\alpha_1=\beta_1$ and $\alpha_2=\beta_2$ and
$\alpha_3<\beta_3$.

How about the function $e^{\sqrt{\,\log n}}@$; where does it
live in the hierarchy? We can answer questions like this by using the rule
\begindisplay
e^{f(n)}\prec e^{g(n)}\quad\iff\quad\lim_{n\to\infty}\bigl(f(n)-g(n)\bigr)=-\infty\,,
\eqno
\enddisplay
which follows in two steps from definition \eq(|prec-def|) by
taking logarithms. Consequently
\begindisplay
1\prec f(n)\prec g(n)\quad\implies\quad e^{\vert f(n)\vert}\prec
 e^{\vert g(n)\vert}\,.
\enddisplay
And since $1\prec\log\log n\prec\sqrt{\mathstrut\log n}\prec\epsilon\log n$,
we have $\log n\prec e^{\sqrt{\,\log n}}\prec n^\epsilon$.

When two functions $f(n)$ and $g(n)$ have the
{\it same\/} rate of growth, we write `$f(n)\asymp g(n)$'.
 The official definition is:
\begindisplay
f(n)\asymp g(n)&\iff\bigl\vert f(n)\bigr\vert\le C\bigl\vert g(n)\bigr\vert\And
	\bigl\vert g(n)\bigr\vert\le C\bigl\vert f(n)\bigr\vert\,,\cr
&\hskip4em\hbox{for some $C$ and for all sufficiently large $n$}.
\eqno\eqref|hardy-asymp-def|\cr
\enddisplay
This holds, for example, if $f(n)$ is constant and $g(n)=\cos n+\arctan n$.
We will
prove shortly that it holds whenever $f(n)$ and $g(n)$ are polynomials
of the same degree. There's also a stronger relation, defined by the rule
\begindisplay
f(n)\sim g(n)\iff \lim_{n\to\infty}{f(n)\over g(n)}=1\,.
\eqno\eqref|asymp-def|
\enddisplay
In this case we say that ``$f(n)$ is asymptotic to $g(n)$.\qback''
"!$\asymp$, $\sim$, $\prec$, and $\succ$"

\def\Lfr{{\frak L}}
G.\thinspace H. "Hardy" [|hardy-tract|] introduced an
 interesting and important concept called
the class of {\it"logarithmico-exponential functions"}, defined recursively as
the smallest family $\Lfr$ of functions satisfying the following properties:
\smallskip
\item{$\bullet$}
The constant function $f(n)=\alpha$ is in $\Lfr$, for all real $\alpha$.\par
\item{$\bullet$}
The identity function $f(n)=n$ is in $\Lfr$.\par
\item{$\bullet$}
If $f(n)$ and $g(n)$ are in $\Lfr$, so is $f(n)-g(n)$.\par
\item{$\bullet$}
If $f(n)$ is in $\Lfr$, so is $e^{f(n)}$.\par
\item{$\bullet$}
If $f(n)$ is in $\Lfr$ and is ``eventually positive,\qback''
then $\ln f(n)$ is in~$\Lfr$.
\smallskip\noindent
A function $f(n)$ is called ``"eventually positive"'' if there is an integer
$n_0$ such that $f(n)>0$ whenever $n\ge n_0$.

We can use these rules to show, for example, that $f(n)+g(n)$ is in $\Lfr$
whenever $f(n)$ and $g(n)$ are, because $f(n)+g(n)=f(n)-\bigl(0-g(n)\bigr)$.
If $f(n)$ and $g(n)$ are eventually positive members of~$\Lfr$, their product
$f(n)@g(n)=e^{\,\ln f(n)+\ln g(n)}$ and quotient $f(n)/g(n)=
e^{\,\ln f(n)-\ln g(n)}$ are in~$\Lfr$; so are functions like
$\sqrt{f(n)}=e^{\half\ln f(n)}$,
etc. Hardy proved that every logarithmico-exponential
function is eventually positive, eventually
negative, or identically zero. Therefore the product and quotient of
any two $\Lfr$-functions is in~$\Lfr$, except that we cannot divide
by a function that's identically zero.

Hardy's main theorem about logarithmico-exponential functions is that they
form an asymptotic hierarchy: {If\/ $f(n)$ and\/ $g(n)$ are any functions
in\/~$\Lfr$, then either\/ $f(n)\prec g(n)$, or\/ $f(n)\succ g(n)$, or\/
$f(n)\asymp g(n)$. In the last case there is, in fact, a constant\/~$\alpha$
such that}
\begindisplay
f(n)\sim\alpha\,g(n)\,.
\enddisplay
The proof of Hardy's theorem is beyond the scope of this book; but it's
nice to know that the theorem exists, because almost every function we
ever need to deal with is in~$\Lfr$. In practice, we can generally fit
a given function into a given hierarchy without great difficulty.

\beginsection 9.2 O Notation

A wonderful notational convention for asymptotic analysis was introduced
by Paul "Bachmann" in 1894 and popularized in
 subsequent years by Edmund "Landau" and others.
\g\noindent\llap{``}\dots\ wir durch das Zeichen\/ $O(n)$ eine Gr\"o\ss e ausdr\"ucken,
deren "O"rdnung in Bezug auf\/ $n$ die Ordnung von\/~$n$ nicht
\"uberschreitet; ob sie wirklich Glieder von der Ordnung\/~$n$
in sich enth\"alt, bleibt bei dem bisherigen Schlu\ss verfahren
dahingestellt.''\par\hfill\kern-4pt\dash---P. Bachmann [|bachmann|]\g
We have seen it in formulas like
\begindisplay
H_n=\ln n+\gamma+O(1/n)\,,
\eqno
\enddisplay
which tells us that the $n$th harmonic number is equal to the natural
logarithm of~$n$ plus Euler's constant, plus a quantity that is
``"Big Oh" of\/ $1$\kern-1pt~over~$n$.\qback'' This last quantity isn't specified
exactly; but whatever it is, the "notation" claims that its absolute
value is no more than a constant times~$1/n$.

The beauty of $O$-notation is that it suppresses unimportant detail
and lets us concentrate on salient features: The quantity $O(1/n)$ is
negligibly small, if constant multiples of~$1/n$ are unimportant.

Furthermore we get to use $O$ right in the middle of a formula. If we
want to express \thiseq\ in terms of the notations in Section~9.1,
we must transpose `$\ln n+\gamma$' to the left side and specify a weaker
result like