chap9.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\enddisplay
We have $f(n)=\Omega\bigl(g(n)\bigr)$ if and only if
$g(n)=O\bigl(f(n)\bigr)$. A sorting algorithm whose running time is
$\Omega(n^2)$ is inefficient compared with one whose running time is
$O(n\log n)$, if $n$ is large enough.

Finally there's "Big Theta", which specifies an
"!$\Theta$"
\g Since\/ $\Omega$ and\/ $\Theta$ are uppercase Greek letters,
the\/ $O$ in\/ $O$\kern-1pt-notation must be a capital Greek Omicron.\par
After all, Greeks invented asymptotics.\g
exact order of growth:
\begindisplay
f(n)=\Theta\bigl(g(n)\bigr)\iff
\tworestrictions{\displaymath f(n)=O\bigl(g(n)\bigr)$}%
 {and\quad\displaymath f(n)=\Omega\bigl(g(n)\bigr)\,.$}
\eqno
\enddisplay
We have $f(n)=\Theta\bigl(g(n)\bigr)$ if and only if $f(n)\asymp g(n)$
in the notation we saw previously, equation \eq(|hardy-asymp-def|).

Edmund "Landau" [|landau-primes|] invented a ``"little oh"'' notation,
\begindisplay \openup-3pt
&f(n)=o\bigl(g(n)\bigr)\cr
&\qquad\iff
\bigl\vert f(n)\bigr\vert\le \epsilon\bigl\vert g(n)\bigr\vert
\qquad\tworestrictions{for all $n\ge n_0(\epsilon)$ and}%
 {for all constants $\epsilon>0$.}
\eqno\eqref|little-o-def|
\enddisplay
This is essentially the relation $f(n)\prec g(n)$ of \eq(|prec-def|).
We also have
\begindisplay
f(n)\sim g(n)\iff f(n)=g(n)+o\bigl(g(n)\bigr)\,.
\eqno
\enddisplay

Many authors use `$o$' in asymptotic formulas, but a more explicit
`$O$' expression is almost always
preferable. For example,
the average running time of a computer method called ``"bubblesort"''
"!sorting" "!$o$, considered harmful"
depends on the asymptotic value of the sum $P(n)=\sum_{k=0}^n k^{n-k\,}k!/n!$.
Elementary asymptotic methods suffice to
prove the formula $P(n)\sim\sqrt{\pi n/2}$, which means that the ratio
$P(n)/\mskip-2mu\sqrt{\pi n/2}$ approaches~$1$ as $n\to\infty$. However, 
the true behavior of $P(n)$ is best understood by considering
the {\it difference}, $P(n)-\sqrt{\pi n/2}$, not the ratio:
\begindisplay \def\preamble{\bigstrut$\hfil##$\enspace%
 &&\vrule##&\enspace\hfil$##$\hfil\enspace}%
	\offinterlineskip
n\,&&P(n)/\mskip-2mu\sqrt{\pi n/2}&&P(n)-\sqrt{\pi n/2}\cr
\omit&height2pt&&\cr
\noalign{\hrule}
\omit&height2pt&&\cr
1&&0.798&&-0.253\cr
%5&&0.853&&-0.411\cr
10&&0.878&&-0.484\cr
%15&&0.893&&-0.518\cr
20&&0.904&&-0.538\cr
30&&0.918&&-0.561\cr
40&&0.927&&-0.575\cr
50&&0.934&&-0.585\cr
\enddisplay
The numerical evidence in the middle column is not very compelling;
it certainly is far from a dramatic proof that $P(n)/\mskip-2mu
\sqrt{\pi n/2}$ approaches~$1$ rapidly, if at all. But the right-hand column
shows that $P(n)$ is
very close indeed to $\displaystyle\sqrt{\pi n/2}$.
Thus we can characterize the behavior
of~$P(n)$ much better if we can derive formulas of the form
\begindisplay
P(n)=\sqrt{\pi n/2}+O(1)\,,
\enddisplay
or even sharper estimates like
\begindisplay
P(n)=\sqrt{\pi n/2}-\textstyle{2\over3}+O(1/\sqrt n\,)\,.
\enddisplay
Stronger methods
of asymptotic analysis are needed to prove $O$-results,
but the additional effort required to learn these stronger methods
is amply compensated by the improved understanding that comes with~$O$-bounds.

Moreover, many sorting algorithms have running times of the form
\begindisplay
T(n)=A\,n\lg n\,+\,B\,n\, +\, O(\log n)
\enddisplay
for some constants $A$ and $B$. Analyses that stop at $T(n)\sim A\,n\lg n$
don't tell the whole story, and it turns out to be a bad strategy to
choose a sorting algorithm based just on its $A$ value. Algorithms with
a good~`$A$' often achieve this at the expense of a bad~`$B$'. Since $n\lg n$
grows only slightly faster than~$n$, the algorithm that's faster asymptotically
(the one with a slightly smaller~$A$~value) might be faster only for
values of~$n$ that never actually arise in practice. Thus, asymptotic
methods that allow us to go past the first term and evaluate~$B$
are necessary if we are to make the right choice of method.

Before we go on to study $O$, let's talk about one more small aspect
of mathematical style. Three different notations for
logarithms have been used in this chapter: "lg", "ln", and~"log". We often
\g Also lD, the Dura\-flame logarithm.\g
use `lg' in connection with computer methods, because binary
logarithms are often relevant in such cases; and we often use `ln'
in purely mathematical calculations, since the formulas for natural
logarithms are nice and simple. But what about `log'? Isn't this the ``common''
base-10 logarithm that students learn in high school\dash---the ``common''
"!common logarithm"
\tabref|nn:log|logarithm that turns out
to be very uncommon in mathematics and computer science? Yes; and many
mathematicians confuse the issue by using `log'
to stand for natural logarithms or binary logarithms.
There is no universal agreement here.
But we can usually breathe a sigh of relief when a logarithm appears inside
$O$-notation, because $O$ ignores multiplicative constants. 
There is no difference between $O(\lg n)$, $O(\ln n)$, and $O(\log n)$, as
$n\to\infty$;
similarly, there is no difference
between $O(\lg\lg n)$, $O(\ln\ln n)$, and $O(\log\log n)$.
\g Notice that\par$\log\log\log n$\par is undefined when\/ $n\le10$.\g
We get to choose whichever we please; and the one with
`log' seems friendlier because it is more pronounceable. 
Therefore we generally use `log' in all contexts where it improves 
readability without introducing ambiguity.

\beginsection 9.3 O Manipulation

Like any mathematical formalism, the $O$-notation has rules of manipulation
that free us from the grungy details of its definition. Once
we prove that the rules are correct, using the definition, we can henceforth
work on a higher plane and forget about actually verifying that one
set of functions is contained in another. We don't even need to calculate the
\g The secret of being a bore is to tell everything.\par
\hfill\dash---"Voltaire"\g
constants $C$ that are implied by each~$O$, as long as we follow rules
that guarantee the existence of such constants.

For example, we can prove once and for all that
\begindisplay \openup2pt
&n^m=O(n^{m'}),\qquad\hbox{when $m\le m'$};\eqno\cr
&O\bigl(f(n)\bigr)+O\bigl(g(n)\bigr)=
 O\bigl(\vert f(n)\vert+\vert g(n)\vert\bigr)\,.
\eqno\eqref|o-f+g|
\enddisplay
Then we can say immediately that ${1\over3}n^3+{1\over2}n^2+{1\over6}n
=O(n^3)+O(n^3)+O(n^3)=O(n^3)$, without the laborious calculations
in the previous section.

Here are some more rules that follow easily from the definition:
\begindisplay
f(n)&=O\bigl(f(n)\bigr)\,;\eqno\eqref|o-identity|\cr
c\cdot O\bigl(f(n)\bigr)&=O\bigl(f(n)\bigr)\,,
 \qquad\hbox{if $c$ is constant};\eqno\cr
O\bigl(O\bigl(f(n)\bigr)\bigr)&=O\bigl(f(n)\bigr)\,;\eqno\cr
O\bigl(f(n)\bigr)@O\bigl(g(n)\bigr)&=O\bigl(f(n)@g(n)\bigr)\,;
 \eqno\eqref|o-prod-in|\cr
O\bigl(f(n)\,g(n)\bigr)&=f(n)@O\bigl(g(n)\bigr)\,.
 \eqno\eqref|o-prod-out|\cr
\enddisplay
Exercise |prove-o-f+g| proves \eq(|o-f+g|), and the proofs of the
others are similar. We can always replace something of the form on the
left by what's on the right, regardless of the side conditions on the
variable~$n$.

Equations \eq(|o-prod-out|) and \eq(|o-identity|) allow us to derive
\g\vskip-20pt
(Note: The formula\/ $O(f(n))^2$ does not denote the set of all functions\/
$g(n)^2$ where\/ $g(n)$ is in $O(f(n))$; such functions $g(n)^2$ cannot
be negative, but the set\/ $O(f(n))^2$ includes negative functions. In general,
when $S$~is a set, the notation\/ $S^2$ stands for the set of all products\/
$s_1s_2$ with $s_1$~and\/~$s_2$ in~$S$, not for the set of all
squares\/ $s^2$ with $s\in S$.)\g
the identity $O\bigl(f(n)^2\bigr)=O\bigl(f(n)\bigr){}^2$. This sometimes
helps avoid parentheses, since we can write
\begindisplay
O(\log n)^2\qquad\hbox{instead of}\qquad O\bigl((\log n)^2\bigr)\,.
\enddisplay
Both of these are preferable to `$O(\log^2 n)$', which is ambiguous
because some authors use it to mean `$O(\log\log n)$'.

Can we also write
\begindisplay
O(\log n)^{-1}\qquad\hbox{instead of}\qquad O\bigl((\log n)^{-1}\bigr)\,?
\enddisplay
No! This is an abuse of notation, since the set of functions $1/O(\log n)$
is neither a subset nor a superset of $O(1/\!@\log n)$. We could legitimately
substitute $\Omega(\log n)^{-1}$ for $O\bigl((\log n)^{-1}\bigr)$, but
this would be awkward. So we'll restrict our use of ``exponents outside
the~$O@$'' to constant, positive integer exponents.

Power series give us some of the most useful operations of all. If the
sum
\begindisplay
S(z)=\sum_{n\ge0}a_n\,z^n
\enddisplay
converges absolutely for some complex number $z=z_0$, then
\begindisplay
S(z)=O(1)\,,\qquad\hbox{for all $\vert z\vert\le\vert z_0\vert$}.
\enddisplay
This is obvious, because
\begindisplay
\vert S(z)\vert\le
\sum_{n\ge0}\vert a_n@\vert\,\vert z\vert^n\le
\sum_{n\ge0}\vert a_n@\vert\,\vert z_0\vert^n=C<\infty\,.
\enddisplay
In particular, $S(z)=O(1)$ as $z\to0$, and $S(1/n)=O(1)$ as $n\to\infty$,
provided only that $S(z)$ converges for at least one nonzero value of~$z$.
We can use this principle to truncate a power series at any convenient
point and estimate the remainder with~$O$. For example, not only is
$S(z)=O(1)$, but
\begindisplay
S(z)&=a_0+O(z)\,,\cr
S(z)&=a_0+a_1z+O(z^2)\,,\cr
%S(z)&=a_0+a_1z+a_2z^2+O(z^3)\,,\cr
\enddisplay
and so on, because
\begindisplay
%S(z)=a_0+a_1z+a_2z^2+z^3\sum_{n\ge3}a_{n-3}z^{n-3}
S(z)=\sum_{0\le k<m}a_kz^k+z^m\sum_{n\ge m}a_nz^{n-m}
\enddisplay
and the latter sum, like $S(z)$ itself, converges absolutely for $z=z_0$
and is $O(1)$.
Table |o-special| lists some of the most useful asymptotic formulas,
half of which are simply based on truncation of power series according
to this rule.

"Dirichlet series", which are sums of the
form $\sum_{k\ge1} a_k/k^z$, can be truncated in a similar way: If a
Dirichlet series converges absolutely when $z=z_0$, we can truncate
it at any term and get the approximation
\begindisplay
\sum_{1\le k<m}a_k/k^z+O(m^{-z})\,,
\enddisplay
valid for $\Re z\ge\Re z_0$.
\g Remember that\/ $\Re$ stands for ``real part.\qback''\g
The asymptotic formula for Bernoulli numbers $B_n$ in Table~|o-special|
illustrates this principle.

On the other hand, the asymptotic formulas for $H_n$, $n!$, and $\pi(n)$
in Table~|o-special| are not truncations of convergent series;
if we extended them indefinitely they would diverge for all values of~$n$.
This is particularly easy to see in the case of $\pi(n)$, since we have
already observed in Section~7.3, Example~5, that the power series
$\sum_{k\ge0}k!/(\ln n)^k$ is everywhere divergent. Yet these truncations
of divergent series turn out to be useful approximations.
%, even if we stop after the first or second term.

\topinsert
\table Asymptotic approximations, valid as $n\to\infty$ and $z\to0$.%
\tabref|o-special|
\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=6pt \openup6.7pt%
 \advance\displayindent-\parindent\advance\displaywidth\parindent
H_n&=\ln n+\gamma
 +{1\over2n}-{1\over12n^2}+{1\over120n^4}+O\Bigl({1\over n^6}\Bigr)\,.
 \eqno\eqref|o-harmonic|\cr
n!&=\sqrt{2\pi n}\,\Bigl({n\over e}\Bigr)^{\!n}\biggl(1+{1\over12n}
 +{1\over288n^2}-{139\over51840n^3}+O\Bigl({1\over n^4}\Bigr)\biggr)\,.
 \eqno\eqref|o-factorial|\cr
B_n&=2\[n\ {\rm even}](-1)^{n/2-1}{n!\over(2\pi)^n}\bigl(1+2^{-n}
 +3^{-n}+O(4^{-n})\bigr)\,.
 \eqno\eqref|o-bernoulli|\cr
\pi(n)&={n\over\ln n}+{n\over(\ln n)^2}+{2!\,n\over(\ln n)^3}
 +{3!\,n\over(\ln n)^4}+O\Bigl({n\over(\log n)^5}\Bigr)\,.
 \eqno\eqref|o-pi|\cr
e^z&=1+z+{z^2\over2!}+{z^3\over3!}+{z^4\over4!}+O(z^5)\,.
 \eqno\eqref|o-exp|\cr
\ln(1+z)&=z-{z^2\over2}+{z^3\over3}-{z^4\over4}+O(z^5)\,.
 \eqno\eqref|o-log|\cr
{1\over1-z}&=1+z+z^2+z^3+z^4+O(z^5)\,.
 \eqno\eqref|o-geom|\cr
(1+z)^\alpha&=1+\alpha z+{\alpha\choose2}z^2+{\alpha\choose3}z^3
 +{\alpha\choose4}z^4+O(z^5)\,.
 \eqno\eqref|o-binomial|\cr
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\endinsert

An asymptotic approximation is said to have {\it"absolute error"\/}
"!error, absolute"
$O\bigl(g(n)\bigr)$ if it~has the form $f(n)+O\bigl(g(n)\bigr)$ where
$f(n)$ doesn't involve~$O$. The approximation has {\it"relative error"\/}
"!error, relative"
$O\bigl(g(n)\bigr)$ if it has the form $f(n)\bigl(1+O\bigl(g(n)\bigr)\bigr)$
where $f(n)$ doesn't involve~$O$. For example, the approximation for~$H_n$
in Table~|o-special| has absolute error~$O(n^{-6})$; the approximation
for $n!$ has relative error~$O(n^{-4})$. (The right-hand side of
\eq(|o-factorial|) doesn't actually have the required form
$f(n)\*{\bigl(1+O(n^{-4})\bigr)}$, but we could rewrite it
\begindisplay
\sqrt{2\pi n}\,\Bigl({n\over e}\Bigr)^{\!n}\biggl(1+{1\over12n}
 +{1\over288n^2}-{139\over51840n^3}\biggr)\bigl(1+O(n^{-4})\bigr)
\enddisplay
if we wanted to; a similar calculation is the subject of exercise |rel-error|.)
\g(Relative error is nice for taking reciprocals, because
$1/(1+O(\epsilon))=1+O(\epsilon)$.)\g
The absolute error of this approximation is $O(n^{n-3.5}e^{-n})$.
Absolute error is related to the number of correct decimal digits
to the right of the decimal point
if the $O$~term is ignored; relative error corresponds to the
number of correct ``significant figures.\qback''

We can use truncation of power series to prove the general laws
\begindisplay
\ln\bigl(1+O(f(n))\bigr)&=O\bigl(f(n)\bigr)\,,
&\qquad\hbox{if\/ $f(n)\prec1$};\eqno\eqref|o-ln|\cr