chap9.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\begindisplay
H_n-\ln n-\gamma\prec{\log\log n\over n}
\enddisplay
or a stronger result like
\begindisplay
H_n-\ln n-\gamma\asymp{1\over n}\,.
\enddisplay
The Big Oh notation allows us to specify an appropriate amount of
detail in~place, without transposition.

The idea of imprecisely specified quantities can be made clearer if
we consider some additional examples. We occasionally use the notation
`$@\pm1@$'
 to stand for something that is either $+1$ or $-1$; we don't
know (or perhaps we don't care) which it is, yet we can manipulate it
in formulas.

N.\thinspace G. "de Bruijn"
 begins his book \kern-1pt{\sl Asymptotic Methods in Analysis\/}~[|de-bruijn|]
by considering a "Big~Ell" notation that helps us understand Big~Oh.
If we write $L(5)$ for a number whose absolute value is less than~$5$
(but we don't say what the number is), then we can perform certain
calculations without knowing the full truth. For example, we can
deduce formulas such as $1+L(5)=L(6)$; $L(2)+L(3)=L(5)$; $L(2)L(3)=L(6)$;
$e^{L(5)}=L(e^5)$; and so on. But we cannot conclude that $L(5)-L(3)=L(2)$,
since the left side might be $4-0$.
In fact, the most we can say is $L(5)-L(3)=L(8)$.

Bachmann's
$O$-notation is similar to $L$-notation but it's even less precise:
$O(\alpha)$ stands for a number whose absolute value is at most a constant
times~$\vert \alpha\vert$. We don't say what the number is and we don't
even say what the constant is. Of course the notion of a ``constant''
is nonsense
\g It's not nonsense, but it is pointless.\g
if there is nothing variable in the picture, so we use $O$-notation only
in contexts when there's at least one quantity (say~$n$) whose value is varying.
The formula
\begindisplay
f(n)=O\bigl(g(n)\bigr)\qquad\hbox{for all $n$}
\eqno\eqref|o-examp|
\enddisplay
means in this context that there is a constant $C$ such that
\begindisplay
\bigl\vert f(n)\bigr\vert\le C\bigl\vert g(n)\bigr\vert\qquad\hbox{for all $n$};
\eqno\eqref|o-def|
\enddisplay
and when $O\bigl(g(n)\bigr)$ stands in the middle of a formula it
represents a function $f(n)$ that satisfies~\thiseq. The values of~$f(n)$
are unknown, but we do know that they aren't too large. Similarly,
de~Bruijn's `$L(n)$' represents an unspecified function~$f(n)$ whose
values satisfy $\bigl\vert f(n)\bigr\vert<\vert n@\vert$. The main difference between
$L$ and~$O$ is that $O$-notation involves an unspecified constant~$C$;
each appearance of~$O$ might involve a different~$C$, but each~$C$ is
\g I've got a little list\dash---I've got a little list,\par
Of annoying terms and details that might well be under ground,\par
And that never would be missed\dash---that never would be missed.
"!Gilbert"\g % Mikado
independent of~$n$.

For example, we know that the sum of the first $n$ squares is
"!sum of consecutive squares"
\begindisplay
\Sq_n=\textstyle
{1\over3}n(n+\half)(n+1)={1\over3}n^3+\half n^2+{1\over6}n\,.
\enddisplay
We can write
\begindisplay
\Sq_n=O(n^3)
\enddisplay
because
$\vert{1\over3}n^3+\half n^2+{1\over6}n@\vert
\le{1\over3}\vert n@\vert^3+\half\vert n@\vert^2+{1\over6}\vert n@\vert
\le{1\over3}\vert n^3\vert+\half\vert n^3\vert+{1\over6}\vert n^3\vert
=\vert n^3\vert$ for all integers~$n$.
Similarly, we have the more specific formula
\begindisplay
\Sq_n=\textstyle{1\over3}n^3+O(n^2)\,;
\enddisplay
we can also be sloppy and throw away information, saying that
\begindisplay
\Sq_n=O(n^{10})\,.
\enddisplay
Nothing in the definition of $O$ requires us to give a best possible bound.

But wait a minute. What if the variable $n$ isn't an integer? What if we
have a formula like $S(x)=
{1\over3}x^3+\half x^2+{1\over6}x$, where $x$~is a real number?
Then we cannot say that $S(x)=O(x^3)$, because the ratio
$S(x)/x^3={1\over3}+\half x^{-1}+{1\over6}x^{-2}$ becomes unbounded when
$x\to0$. And we cannot say that $S(x)=O(x)$, because the ratio
$S(x)/x={1\over3}x^2+\half x+{1\over6}$ becomes unbounded when $x\to\infty$.
So we apparently can't use $O$-notation with~$S(x)$.

The answer to this dilemma is that variables used with $O$ are generally
subject to side conditions. For example, if we stipulate that $\vert x\vert
\ge1$, or that $x\ge\epsilon$ where $\epsilon$ is any positive constant,
or that $x$ is an integer,
then we can write $S(x)=O(x^3)$. If we stipulate that $\vert x\vert\le1$,
or that $\vert x\vert\le c$ where $c$ is any positive constant, then we
can write $S(x)=O(x)$. The $O$-notation is governed by its environment,
by constraints on the variables involved.

These constraints are often specified by a limiting relation.
For example, we might say that
\begindisplay
f(n)=O\bigl(g(n)\bigr)\qquad\hbox{as $n\to\infty$}.
\eqno
\enddisplay
This means that the $O$-condition is supposed to hold when $n$ is ``near''~%
$\infty$; we don't care what happens unless $n$ is quite large. Moreover,
we don't even specify exactly what ``near'' means; in such cases each
appearance of~$O$ implicitly asserts the existence of {\it two\/}
constants $C$ and~$n_0$, such that
\begindisplay
\bigl\vert f(n)\bigr\vert\le C\bigl\vert g(n)\bigr\vert
\qquad\hbox{whenever $n\ge n_0$}.
\eqno\eqref|o-def-limit|
\enddisplay
The values of $C$ and $n_0$ might be different for each $O$, but they do
not depend on~$n$. Similarly, the notation
\g You are the fairest\par\quad of your sex,\par
Let me be your\par\quad hero;\par
I love you as\par
\quad one over $x$,\par
As $x$ approaches\par\quad zero.\par
Positively.\g
\begindisplay
f(x)=O\bigl(g(x)\bigr)\qquad\hbox{as $x\to0$}
\enddisplay
means that there exist two constants $C$ and $\epsilon$ such that
\begindisplay
\bigl\vert f(x)\bigr\vert\le C\bigl\vert g(x)\bigr\vert
 \qquad\hbox{whenever $\vert x\vert\le \epsilon$}.
\eqno\eqref|o-def-limit0|
\enddisplay
The limiting value does not have to be $\infty$ or $0@$; we can write
\begindisplay
\ln z=z-1+O\bigl((z-1)^2\bigr)\qquad\hbox{as $z\to1$},
\enddisplay
because it can be proved that $\vert\ln z-z+1\vert\le\vert z-1\vert^2$
when $\vert z-1\vert\le\half$.

Our definition of $O$ has gradually developed, over a few pages,
 from something that seemed
pretty obvious to something that seems rather complex; we now have
$O$ representing an undefined function and either one or two unspecified
constants, depending on the environment. This may seem complicated enough
for any reasonable notation, but it's still not the whole story! Another
subtle consideration lurks in the background. Namely, we need to
realize that it's fine to write
\begindisplay
\textstyle{1\over3}n^3+\half n^2+{1\over6}n=O(n^3)\,,
\enddisplay
but we should {\it never\/} write this equality with the sides reversed.
Otherwise we could deduce ridiculous things like $n=n^2$ from the
identities $n=O(n^2)$ and $n^2=O(n^2)$. When we work with $O$-notation
and any other formulas that involve imprecisely specified quantities,
\g\noindent\llap{``}And to auoide the tediouse repetition of these woordes: is equalle to:
I~will sette as I doe often in woorke use, a paire of paralleles,
or Gemowe lines of one lengthe, thus: $=\joinrel=\joinrel=\joinrel=\,$,
bicause noe~.2.\ thynges, can be moare equalle.''\par
\hfill\dash---R. "Recorde" [|recorde-wit|]\g
we are dealing with {\it"one-way equalities"}. The right side of an
"!equality, one-way"
equation does not give more information than the left side, and it may
give less; the right is a ``crudification'' of the left.

From a strictly formal point of view, the notation
$O\bigl(g(n)\bigr)$ does not stand for a single function~$f(n)$, but
for the {\it set\/} of all functions~$f(n)$ such that
$\bigl\vert f(n)\bigr\vert\le C\bigl\vert g(n)\bigr\vert$ for some constant~$C$.
An ordinary formula~$g(n)$ that doesn't involve $O$-notation stands for the
set containing a single function $f(n)=g(n)$. If $S$ and~$T$ are sets
of functions of~$n$, the notation $S+T$ stands for the set of all
functions of the form $f(n)+g(n)$, where $f(n)\in S$ and $g(n)\in T$;
other notations like $S-T$, $ST$, $S/T$, $\sqrt S$, $e^S$, $\ln S$
are defined similarly. Then an ``equation'' between such sets of functions
is, strictly speaking, a {\it"set inclusion"\/}; the `$=$' sign really
means `$\subseteq$'. These formal definitions put all of our
$O$~manipulations on firm logical ground.

For example, the ``equation''
\begindisplay
\textstyle {1\over3}n^3+O(n^2)=O(n^3)
\enddisplay
means that $S_1\subseteq S_2$, where $S_1$ is the set of all functions
of the form ${1\over3}n^3+f_1(n)$ such that there exists a constant~$C_1$
with $\bigl\vert f_1(n)\bigr\vert\le C_1\vert n^2\vert$, and where
$S_2$ is the set of all functions
$f_2(n)$ such that there exists a constant~$C_2$
with $\bigl\vert f_2(n)\bigr\vert\le C_2\vert n^3\vert$.
We can formally prove this ``equation'' by taking an arbitrary element of
the left-hand side and showing that it belongs to the right-hand side:
Given
${1\over3}n^3+f_1(n)$ such that $\bigl\vert f_1(n)\bigr\vert\le C_1\vert n^2\vert$,
we must prove that there's a
constant~$C_2$
such that $\vert{1\over3}n^3+ f_1(n)\vert\le C_2\vert n^3\vert$.
The constant $C_2={1\over3}+C_1$ does the trick, since
$n^2\le\vert n^3\vert$ for all integers~$n$.

If `$=$' really means `$\subseteq$',
why don't we use `$\subseteq$'
instead of abusing the equals sign?
"!notation"
There are four reasons.

First, tradition.
Number theorists started using the equals~sign
with $O$-notation and the practice stuck.
It's sufficiently well established by now that
we cannot hope to get the mathematical community to change.

Second, tradition.
Computer people are quite used to seeing equals~signs abused\dash---%
for years "FORTRAN" and "BASIC" programmers have been writing
assignment statements like `$N = N+1$'.
One more abuse isn't much.

Third, tradition.
We often read `$=$' as the word `is'.
For instance we verbalize the formula $H_n = O(\log n)$ by saying
``$H$~sub~$n$ is Big~Oh of log~$n$.\qback''
And in English, this~`is' is one-way.
We say that a bird is an animal,
but we don't say that an animal is a bird;
``animal'' is a "crudification" of ``bird.\qback''

Fourth, for our purposes it's natural.
\g \noindent\llap{``}It is obvious that the sign\/~$=$ is really the wrong sign
for such relations, because it suggests symmetry, and there is
no such symmetry. \dots\ Once this warning has been given, there is,
however, not much harm in using the sign\/~$=$, and we shall maintain~it,
for no other reason than that it is customary.''\par
\hfill\kern-4pt\dash---N.\thinspace G.\thinspace de\thinspace
  Bruijn\thinspace [|de-bruijn|]"!de Bruijn"\g
If we limited our use of $O$-notation to situations where
it occupies the whole right side of a formula\dash---as in
the harmonic number approximation $H_n = O(\log n)$,
or as in the description of a sorting algorithm's
running time $T(n) = O (n \log n)$\dash---%
it wouldn't matter whether we used `$=$'
or something else.
But when we use $O$-notation in the middle of an expression,
as we usually do in asymptotic calculations,
our intuition is well satisfied if we think of
the equals~sign as an equality, and if we
think of something like $O(1/n)$ as a very small quantity.

So we'll continue to use `$=$',
and we'll continue to regard~$O\bigl(g(n)\bigr)$ as
an incompletely specified function,
knowing that we can always fall back on the
set-theoretic definition if we must.

But we ought to mention one more technicality while we're picking nits
about definitions: If there are several variables in the environment,
$O$-notation formally represents sets of functions of two or more
variables, not just one. The domain of each function is every variable
that is currently ``free'' to vary.

 This concept can be a bit subtle,
because a variable might be defined only in parts of an expression, when
it's controlled by a $\sum$ or something similar. For example, let's
look closely at the equation
\begindisplay
\sum_{k=0}^n\,\bigl(k^2+O(k)\bigr)={\textstyle{1\over3}}n^3+O(n^2)\,,
\qquad\hbox{integer $n\ge0$}.
\eqno
\enddisplay
The expression $k^2+O(k)$ on the left stands for the set of all two-variable
functions of the form $k^2+f(k,n)$ such that there exists a constant~$C$
with $\bigl\vert f(k,n)\bigr\vert\le Ck$ for $0\le k\le n$. The sum of
this set of functions, for $0\le k\le n$, is the set of all functions~$g(n)$
of the form
\begindisplay
\sum_{k=0}^n\bigl(k^2{+}f(k,n)\bigr)=\textstyle
{1\over3}n^3+\half n^2+{1\over6}n+f(0,n)+f(1,n)+\cdots+f(n,n)\,,
\enddisplay
where $f@$ has the stated property. Since we have
\begindisplay
&\textstyle
\bigl\vert\half n^2+{1\over6}n+f(0,n)+f(1,n)+\cdots+f(n,n)\bigr\vert\cr
&\qquad\le\textstyle\half n^2+{1\over6}n^2+C\cdt0+C\cdt1+\cdots+C\cdt n\cr
&\qquad<n^2+C(n^2+n)/2<(C+1)n^2\,,
\enddisplay
all such functions $g(n)$ belong to the right-hand side of~\thiseq;
\g(Now is a good time to do warmup exercises
|o-fallacy| and~|o-vanishing|.)\g
therefore \thiseq\ is true.

People sometimes abuse $O$-notation by assuming that it gives an exact
order of growth; they use it as if it specifies a lower bound as well as
an upper bound. For example, an algorithm to sort $n$~numbers might be
called inefficient ``because its running time is~$O(n^2)$.\qback''
But a running time of~$O(n^2)$ does not imply that the running time is
not also~$O(n)$. There's another notation, "Big~Omega", for
"!$\Omega$"
lower bounds:
\begindisplay
f(n)=\Omega\bigl(g(n)\bigr)\iff
\bigl\vert f(n)\bigr\vert\ge C\bigl\vert g(n)\bigr\vert
\qquad\hbox{for some $C>0$.}
\eqno