\documentclass[12pt,twoside]{article}
\usepackage{light}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\lecture{Sums, Approximations, and Asymptotics II}{October 14, 2004}

\section{Block Stacking}

How far can a stack of identical blocks overhang the end of a table
without toppling over?  Can a block be suspended \textit{entirely
beyond} the table's edge?

\begin{center}
\unitlength=0.2in
\begin{picture}(5.5,7)(-3,-2)
\thinlines
\put(-2.5,0){\framebox(3.0,1.0){}}
\put(-1.5,1){\framebox(3.0,1.0){}}
\put(-1,2){\framebox(3.0,1.0){}}
\put(-1.5,3){\framebox(3.0,1.0){}}
\put(-0.5,4){\framebox(3.0,1.0){}}
\thicklines
\put(0,0){\line(-1,0){6}}
\put(0,0){\line(0,-1){2}}
\put(-3,-1){\makebox(0,0){Table}}
\end{picture}
\end{center}

Physics imposes some constraints on the arrangement of the blocks.  In
particular, the stack falls off the desk if its center of mass lies
beyond the desk's edge.  Moreover, the center of mass of the top $k$
blocks must lie above the $(k+1)$-st block; otherwise, the top $k$
would fall over.

In order to find the best configuration of blocks satisfying these
constraints, we'll need a fact about centers of mass.

\begin{fact}
\label{fact:com}
If two objects have masses $m_1$ and $m_2$ and centers-of-mass at
positions $z_1$ and $z_2$, then the center of mass of the two objects
together is at position:
%
\[
\frac{z_1 m_1 + z_2 m_2}{m_1 + m_2}
\]
\end{fact}

Define the \textit{offset} of a particular configuration of blocks to
be the horizonal distance from its center of mass to its rightmost
edge.
%
\begin{center}
\unitlength=0.3in
\begin{picture}(8.25,5.25)(-6,-1)
\thinlines
\put(-2,0){\framebox(3.0,1.0){}}
\put(-1,1){\framebox(3.0,1.0){}}
\put(0,1.5){\circle*{0.2}}
\put(-4,1.5){\makebox(0,0){center of mass}}
\put(-2,1.5){\vector(1,0){1.8}}
\put(-1.5,2){\framebox(3.0,1.0){}}
\put(0,4){\vector(0,-1){1}}
\put(2,4){\vector(0,-1){2}}
\put(1,4){\makebox(0,0){offset}}
\thicklines
\put(0,0){\line(-1,0){6}}
\put(0,0){\line(0,-1){1}}
\put(-3,-0.5){\makebox(0,0){Table}}
\end{picture}
\end{center}
%
The offset determines precisely how far that configuration can extend
beyond the desk since at best the center of mass lies right above the
desk's edge.  So hereafter we can focus on maximizing the
\textit{offset} of a stack of $n$ blocks rather than the
\textit{overhang}.  As a result, we need only be concerned with
whether the stack is internally stable and not with whether the whole
configuration is too far to the right and falls off the table.

We can establish the greatest possible offset of a stack of $n$ blocks
with an inductive argument.  This is an instance where induction not
only serves as a proof technique, but also turns out to be a nice tool
for reasoning about the problem.

\begin{theorem}
\label{th:block-stacking}
The greatest possible offset of a stack of $n \geq 1$ blocks is:
%
\[
X_n = \frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots + \frac{1}{2n}
\]
\end{theorem}

\begin{proof}
We use induction on $n$, the number of blocks.  Let $P(n)$ be the
proposition that the greatest possible offset of a stack of $n \geq 1$
blocks is $1/2 + 1/4 + \ldots + 1/(2n)$.

\noindent \textit{Base case:} For a single block, the center of mass
is distance $X_1 = 1/2$ from its rightmost edge.  So the offset is
$1/2$ and $P(1)$ is true.

\noindent \textit{Inductive step:} For $n \geq 2$, we assume that
$P(n-1)$ is true in order to prove $P(n)$.  A stack of $n$ blocks
consists of the bottom block together with a stack of $n - 1$ blocks
on top.

In order to acheive the greatest possible offset with $n$ blocks, the
top $n-1$ blocks should themselves have the greatest possible offset,
which is $X_{n-1}$; otherwise, we could do better by replacing the top
$n-1$ blocks with a different configuration that has greater offset.
Furthermore, the center of mass of the top $n - 1$ blocks should lie
directly above the right edge of the bottom block; otherwise, we could
do better by sliding the top $n - 1$ blocks farther to the right.

\begin{center}
\unitlength=0.03in
\begin{picture}(70,40)
\thinlines
\put(0,0){\framebox(30,10){}}
\put(15,5){\circle*{2}}
\put(45,5){\makebox(0,0){$X_{n-1} + \frac{1}{2}$}}
\put(33,5){\vector(-1,0){17}}
\put(58,5){\vector(1,0){12}}
\put(10,10){\dashbox(60,30){}}
\put(30,25){\circle*{2}}
\put(40,35){\makebox(0,0){$n-1$ blocks}}
\put(50,25){\makebox(0,0){$X_{n-1}$}}
\put(42,25){\vector(-1,0){11}}
\put(59,25){\vector(1,0){11}}
\end{picture}
\end{center}

We've now identified the configuration of $n$ blocks with the greatest
possible offset.  What remains is to determine what that offset is.
To that end, we'll apply Fact~\ref{fact:com} where positions are
measured relative to the rightmost edge of the $n$-block stack.  In
particular, we have $n-1$ blocks with center of mass at position
$X_{n-1}$, and 1 block with center of mass at position $X_{n-1} +
\frac{1}{2}$.  So Fact~\ref{fact:com} implies that the maximum
possible offset of a stack of $n$ blocks is:
%
\begin{align*}
X_n & = \frac{X_{n-1} \cdot (n-1) + (X_{n-1} + \frac{1}{2}) \cdot 1}{n} \\
    & = X_{n-1} + \frac{1}{2n} \\
    & = \frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots + \frac{1}{2n}
\end{align*}
%
We use the assumption $P(n-1)$ in the last step.  This proves $P(n)$.

The theorem follows by the principle of induction.
\end{proof}

\subsection{Harmonic Numbers}

Sums similar to the one in Theorem~\ref{th:block-stacking} come up all
the time in computer science.  In particular,
%
\[
\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}
\]
%
is called a \term{harmonic sum}.  Its value is called the
\term{$\mathbf{n}$-th harmonic number} and is denoted $H_n$.  In these
terms, the greatest possible offset of a stack of $n$ blocks is
$\frac{1}{2} H_n$.

We can tabulate the maximum achievable overhang with $n = 1$, 2, 3 and
4 blocks by computing the first few harmonic numbers:
%
\[
\begin{array}{cl}
\text{\# of blocks} & \text{maximum overhang} \\ \hline
\\
1 & \frac{1}{2} H_1 = \frac{1}{2}(\frac{1}{1}) = \frac{1}{2} \\
\\
2 & \frac{1}{2} H_2 = \frac{1}{2}(\frac{1}{1} + \frac{1}{2}) = \frac{3}{4} \\
\\
3 & \frac{1}{2} H_3 = \frac{1}{2}(\frac{1}{1} + \frac{1}{2} + \frac{1}{3}) = \frac{11}{12} \\
\\
4 & \frac{1}{2} H_4 = \frac{1}{2}(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}) = \frac{25}{24} > 1
\end{array}
\]
%
The last line reveals that we can suspend the \textit{fourth} block
beyond the edge of the table!  Here's the configuration that does the
trick:

\begin{center}
\unitlength=3pt
\begin{picture}(74,48)(-24,-16)
%\put(-24,-16){\framebox(74,48){}}
\thinlines
\put(27,-4){\makebox(0,0){$\frac{1}{8}$}}
\put(3,0){\framebox(24,8){}} \put(30,4){\makebox(0,0){$\frac{1}{6}$}}
\put(7,8){\framebox(24,8){}} \put(34,12){\makebox(0,0){$\frac{1}{4}$}}
\put(13,16){\framebox(24,8){}} \put(42,20){\makebox(0,0){$\frac{1}{2}$}}
\put(25,24){\framebox(24,8){}}
\thicklines
\put(24,0){\line(-1,0){48}}
\put(24,0){\line(0,-1){16}}
\end{picture}
\end{center}

\subsection{Bounding a Sum with an Integral}

We need to know more about harmonic sums to determine what can be done
with a large number of blocks.  Unfortunately, there is no closed form
for $H_n$.  But, on the bright side, we can get good lower and upper
bounds on harmonic sums using a general technique involving
integration that applies to many other sums as well.

Here's how it works.  First, we imagine a bar graph where the area of
the $k$-th bar is equal to the $k$-th term in the sum.  In particular,
each bar has width 1 and height equal to the value of the $k$-th term.
For example, the bar graph corresponding to the harmonic sum
%
\[
H_n = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}
\]
%
is shown below.

\begin{center}
\unitlength=0.4in
\begin{picture}(9.5,6)(-0.5,-1)
%\put(-0.5,-1){\dashbox(9.5,6){}}
\put(0.000000,0){\framebox(1.0,4.000000){}}
\put(1.000000,0){\framebox(1.0,2.000000){}}
\put(2.000000,0){\framebox(1.0,1.333333){}}
\put(3.000000,0){\framebox(1.0,1.000000){}}
%\put(4.000000,0){\framebox(1.0,0.800000){}}
%\put(5.000000,0){\framebox(1.0,0.666667){}}
%\put(6.000000,0){\framebox(1.0,0.571429){}}
\put(7.000000,0){\framebox(1.0,0.500000){}}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(7,-0.5){\makebox(0,0){$n-1$}}
\put(8,-0.5){\makebox(0,0){$n$}}
\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){5}}
\put(0.5,0.5){\makebox(0,0){$\frac{1}{1}$}}
\put(1.5,0.5){\makebox(0,0){$\frac{1}{2}$}}
\put(2.5,0.5){\makebox(0,0){$\frac{1}{3}$}}
\put(3.5,0.5){\makebox(0,0){$\frac{1}{4}$}}
\put(5.5,0.5){\makebox(0,0){$\ldots$}}
\put(-0.5,4){\makebox(0,0){$1$}}
\put(-0.5,2){\makebox(0,0){$1/2$}}
\end{picture}
\end{center}

Now the \textit{value of the sum is equal to the area of the bars},
and we can estimate the area of the bars using integration.  Suppose
we draw a smooth curve that runs just below the bars; in fact, there's
a natural choice: the curve described by the function $y = 1/(x+1)$.
%
\begin{center}
\unitlength=0.4in
\begin{picture}(9.5,6)(-0.5,-1)
%\put(-0.5,-1){\dashbox(9.5,6){}}
\put(0.000000,0){\framebox(1.0,4.000000){}}
\put(1.000000,0){\framebox(1.0,2.000000){}}
\put(2.000000,0){\framebox(1.0,1.333333){}}
\put(3.000000,0){\framebox(1.0,1.000000){}}
%\put(4.000000,0){\framebox(1.0,0.800000){}}
%\put(5.000000,0){\framebox(1.0,0.666667){}}
%\put(6.000000,0){\framebox(1.0,0.571429){}}
\put(7.000000,0){\framebox(1.0,0.500000){}}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(7,-0.5){\makebox(0,0){$n-1$}}
\put(8,-0.5){\makebox(0,0){$n$}}
\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){5}}
\put(0.5,0.5){\makebox(0,0){$\frac{1}{1}$}}
\put(1.5,0.5){\makebox(0,0){$\frac{1}{2}$}}
\put(2.5,0.5){\makebox(0,0){$\frac{1}{3}$}}
\put(3.5,0.5){\makebox(0,0){$\frac{1}{4}$}}
\put(-0.5,4){\makebox(0,0){$1$}}
\put(-0.5,2){\makebox(0,0){$1/2$}}
\qbezier(0.000000,4.000000)(0.333333,2.666667)(1.000000,2.000000)
\qbezier(1.000000,2.000000)(1.400000,1.600000)(2.000000,1.333333)
\qbezier(2.000000,1.333333)(2.428571,1.142857)(3.000000,1.000000)
\qbezier(3.000000,1.000000)(3.444444,0.888889)(4.000000,0.800000)
\qbezier(4.000000,0.800000)(4.454545,0.727273)(5.000000,0.666667)
\qbezier(5.000000,0.666667)(5.461538,0.615385)(6.000000,0.571429)
\qbezier(6.000000,0.571429)(6.466667,0.533333)(7.000000,0.500000)
\qbezier(7.000000,0.500000)(7.470588,0.470588)(8.000000,0.444444)
\put(5.5,1.1){\makebox(0,0){$y = 1/(x+1)$}}
\end{picture}
\end{center}
%
The area of the bars is at least the area under this curve, so we have
a lower bound on the $n$-th harmonic sum:
%
\begin{align*}
H_n & = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \\
    & \geq \int_0^n \frac{1}{x+1}\ dx \\
    & = \ln(n + 1)
\end{align*}

Remember that $n$ blocks can overhang the edge of a table by
$\frac{1}{2} H_n$ block widths.  So if we had, say, a million blocks,
then this lower bound implies that we could achieve an overhang of at
least
%
\[
\frac{\ln(1,000,000 + 1)}{2} = 6.907\ldots
\]
%
block widths!  In fact, since the lower bound of $\frac{1}{2} \ln(n +
1)$ grows arbitrarily large, there is \textit{no limit} on how far the
stack can overhang.  Of course, this assumes no breeze, deformation of
the blocks, or gravitational variation as our stack grows thousands of
miles high.

We can get an upper bound on the $n$-th harmonic number by playing
essentially the same game.  Now we need a curve that skims just above
the bar graph.  The curve defined by $y = 1 / x$ fits the bill.
%
\begin{center}
\unitlength=0.4in
\begin{picture}(9.5,6)(-0.5,-1)
%\put(-0.5,-1){\dashbox(9.5,6){}}
\put(0.000000,0){\framebox(1.0,4.000000){}}
\put(1.000000,0){\framebox(1.0,2.000000){}}
\put(2.000000,0){\framebox(1.0,1.333333){}}
\put(3.000000,0){\framebox(1.0,1.000000){}}
%\put(4.000000,0){\framebox(1.0,0.800000){}}
%\put(5.000000,0){\framebox(1.0,0.666667){}}
%\put(6.000000,0){\framebox(1.0,0.571429){}}
\put(7.000000,0){\framebox(1.0,0.500000){}}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(7,-0.5){\makebox(0,0){$n-1$}}
\put(8,-0.5){\makebox(0,0){$n$}}
\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){5}}
\put(0.5,0.5){\makebox(0,0){$\frac{1}{1}$}}
\put(1.5,0.5){\makebox(0,0){$\frac{1}{2}$}}
\put(2.5,0.5){\makebox(0,0){$\frac{1}{3}$}}
\put(3.5,0.5){\makebox(0,0){$\frac{1}{4}$}}
\put(-0.5,4){\makebox(0,0){$1$}}
\put(-0.5,2){\makebox(0,0){$1/2$}}
\qbezier(0.800000,5.000000)(0.888889,4.444444)(1.000000,4.000000)
\qbezier(1.000000,4.000000)(1.333333,2.666667)(2.000000,2.000000)
\qbezier(2.000000,2.000000)(2.400000,1.600000)(3.000000,1.333333)
\qbezier(3.000000,1.333333)(3.428571,1.142857)(4.000000,1.000000)
\qbezier(4.000000,1.000000)(4.444444,0.888889)(5.000000,0.800000)
\qbezier(5.000000,0.800000)(5.454545,0.727273)(6.000000,0.666667)
\qbezier(6.000000,0.666667)(6.461538,0.615385)(7.000000,0.571429)
\qbezier(7.000000,0.571429)(7.466667,0.533333)(8.000000,0.500000)
\put(2.5,3.2){\makebox(0,0){$y = 1/x$}}
\end{picture}
\end{center}
%
The area under this curve is an upper bound on the area of the bar
graph and thus on the $n$-th harmonic sum.  But there's a problem: the
area under the curve is infinite because $y = 1 / x$ has a bad
asymptote at $x = 0$.  This is a common problem when bounding sums
with integrals and there's a simple solution: take the \textit{exact}
value of the first term $(1/1)$ and then bound the remaining terms
($1/2 + 1/3 + \ldots + 1/n$) with an integral.  In this case, we get
the upper bound:
%
\begin{align*}
H_n & = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \\
    & \leq 1 + \int_1^n \frac{1}{x}\ dx \\
    & = 1 + \ln n
\end{align*}

So even though there is no closed-form for the $n$-th harmonic sum, we
now know that the harmonic numbers grow logarithmically:
%
\[
\ln(n + 1) \leq H_n \leq 1 + \ln n
\]

There is a refinement to the integration method we've just employed,
called \textit{Euler-Maclaurin summation}, which yields a sequence of
terms that correct errors in the inital estimate.  This technique
gives an absurdly accurate formula for harmonic numbers:
%
\[
H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon(n)}{120n^4}
\]
%
The second term is \term{Euler's constant}, $\gamma =
0.577215664\ldots$.  This is probably the third most important
mathematical constant behind $e$ and $\pi$.  It is somewhat
mysterious; for example, no one knows whether $\gamma$ is rational or
irrational, though if it equals a ratio of integers, then the
denominator must be at least $10^{242,080}$.  In the final term of the
formula above, $\epsilon(n)$ denotes some number between 0 and 1.
You'll never need this kind of precision in this course or, probably,
anywhere else.

\section{The Factorial Function}

One of the most common elements in messy mathematical expressions is
the factorial function:
%
\[
n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n
\]
%
Factorial comes up particularly often in combinatorics and
probability, which happen to be the major topics in the remainder of
6.042.  Within a few weeks, you are going to have factorials coming
out your ears.

A good way to deal with any product is to covert it into a sum by
taking a logarithm:
%
\[
\ln\left( \prod_{k=1}^n f(k) \right) = \sum_{k=1}^n \ln f(k)
\]
%
Then we can apply all our summing tools and exponentiate at the end to
undo the effect of the log.  Let's use this strategy to get bounds on
$n!$.  First, we take a logarithm to make the product into a sum:
%
\begin{align*}
\ln n!
  & = \ln(1 \cdot 2 \cdot 3 \cdots n) \\
  & = \ln 1 + \ln 2 + \ln 3 + \ldots + \ln n
\end{align*}

This sum is rather nasty, but we can still get bounds by the
integration method.  A picture can be \textit{extremely helpful} in
working out the proper bounding functions and limits of integration.

\begin{center}
\unitlength=0.35in
\begin{picture}(8.5,5.5)(-0.5,-1.0)
\qbezier(0.000000,0.000000)(0.386294,0.772589)(1.000000,1.386294)
\qbezier(1.000000,1.386294)(1.432791,1.819085)(2.000000,2.197225)
\qbezier(2.000000,2.197225)(2.452185,2.498681)(3.000000,2.772589)
\qbezier(3.000000,2.772589)(3.462871,3.004024)(4.000000,3.218876)
\qbezier(4.000000,3.218876)(4.469647,3.406735)(5.000000,3.583519)
\qbezier(5.000000,3.583519)(5.474329,3.741628)(6.000000,3.891820)
\qbezier(6.000000,3.891820)(6.477758,4.028323)(7.000000,4.158883)
\qbezier(7.000000,4.158883)(7.480379,4.278978)(8.000000,4.394449)
\put(0.000000,0){\framebox(1.0,0.000000){}}
\put(1.000000,0){\framebox(1.0,1.386294){}}
\put(2.000000,0){\framebox(1.0,2.197225){}}
\put(3.000000,0){\framebox(1.0,2.772589){}}
%\put(4.000000,0){\framebox(1.0,3.218876){}}
%\put(5.000000,0){\framebox(1.0,3.583519){}}
%\put(6.000000,0){\framebox(1.0,3.891820){}}
\put(7.000000,0){\framebox(1.0,4.158883){}}
\qbezier(1.000000,0.000000)(1.386294,0.772589)(2.000000,1.386294)
\qbezier(2.000000,1.386294)(2.432791,1.819085)(3.000000,2.197225)
\qbezier(3.000000,2.197225)(3.452185,2.498681)(4.000000,2.772589)
\qbezier(4.000000,2.772589)(4.462871,3.004024)(5.000000,3.218876)
\qbezier(5.000000,3.218876)(5.469647,3.406735)(6.000000,3.583519)
\qbezier(6.000000,3.583519)(6.474329,3.741628)(7.000000,3.891820)
\qbezier(7.000000,3.891820)(7.477758,4.028323)(8.000000,4.158883)
\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){4.5}}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(8,-0.5){\makebox(0,0){$n$}}
\put(5.8,2.7){\makebox(0,0){$y = \ln x$}}
\put(3,3.8){\makebox(0,0){$y = \ln(x+1)$}}
\put(2.5,0.5){\makebox(0,0){$\ln 3$}}
\put(3.5,0.5){\makebox(0,0){$\ln 4$}}
\put(7.5,0.5){\makebox(0,0){$\ln n$}}
\end{picture}
\end{center}

\noindent In this case, we get the bounds:
%
\[
\begin{array}{rcccl}
{\displaystyle \int_1^n \ln x \ dx}
& \leq &
\ln n!
& \leq &
{\displaystyle \int_0^n \ln(x+1) \ dx} \\
\\
{\displaystyle \Bigl. x \ln x - x \Bigr|_1^n}
& \leq &
\ln n!
& \leq &
{\displaystyle \Bigl. (x+1) \ln(x+1) - (x+1) \Bigr|_0^n}
\\
n \ln n - n + 1
& \leq &
\ln n!
& \leq &
(n + 1) \ln(n+1) - (n+1) + 1
\end{array}
\]
%
Finally, we exponentiate to get bounds on $n!$.
%
\[
\begin{array}{rcccl}
{\displaystyle \paren{\frac{n}{e}}^n \cdot e}
& \leq & n! & \leq &
{\displaystyle \paren{\frac{n+1}{e}}^{n+1} \cdot e}
\end{array}
\]

This gives some indication how big $n!$ is: about $(n/e)^n$.  This
estimate is often good enough.  If you need a little more accuracy,
you can add one more term to get \term{Stirling's Formula}:
%
\[
n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n
\]
%
Stirling's formula is worth committing to memory.  We'll often use it
to rewrite expressions involving $n!$.  Now, one might object that the
expression on the \textit{left} actually looks a lot better than the
expression on the \textit{right}.  But that's just an artifact of
notation.  If you actually wanted to compute $n!$, you'd need $n - 1$
multiplications.  However, the expression on the right is a closed
form; evaluating it requires only a handful of basic operations,
regardless of the value of $n$.  Furthermore, when $n!$ appears inside
a larger expression, you usually can't do much with it.  It doesn't
readily cancel or combine with other terms.  In contrast, the
expression on the right looks scary, but melds nicely into larger
formulas.  So don't be put off: Stirling's Formula is your friend.

(Stepping back a bit, Stirling's formula is fairly amazing.  Who would
guess that the product of the first $n$ positive \textit{integers}
could be so precisely described by a formula involving both $e$ and
$\pi$?)

If you're feeling a little crazy, you might pull out these
even-more-precise bounds:
%
\[
\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{1/(12n+1)}
\ \leq \ n! \ \leq \ 
\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{1/(12n)}
\]
%
These bounds are ridiculously close.  For example, if $n = 100$, then
we get:
%
\begin{align*}
100! & \geq \left( \frac{100}{e} \right)^{100} \sqrt{200 \pi}
            \underbrace{\ e^{1/1201}\ }_{=1.000832\ldots} \\
100! & \leq \left( \frac{100}{e} \right)^{100} \sqrt{200 \pi}
            \underbrace{\ e^{1/1200}\ }_{=1.000833\ldots}
\end{align*}
%
The upper bound is less than 7 hundred-thousandths of 1\% greater than
the lower bound!
%%% revised to here %%%

\section{Asymptotic Notation}

% analogy to the force

Our final topic is a special notation--- called \term{asymptotic
notation}--- designed to sweep mathematical messes under the rug.
Asymptotic notation is sort of like the Force from Star Wars.  It's
everywhere.  Tt's an essential part of the language of computer
science.  And mostly it is a tool for good.  At best, asymptotic
notation suppresses irrelevant detailss, while allowing the essential
features of a mathematical analysis to shine through.  However, as
we'll see, asymptotic notation also has an alluring dark side.

\subsection{Asymptotic Notation:  The Jedi Perspective}

Suppose you want to know how long a computer takes to multiply two $n
\times n$ matrices.  You \textit{could} tally up all the
multiplications and additions and loop variable increments and
comparisons and perhaps factor in hardware-specific considerations
such as page faults and cache misses and branch mispredicts and
floating-point unit availability and all this would give you one sort
of answer.  (Whew!)  Such an answer would be very accurate, but not
very insightful.  Given a very complicated formula for the running
time, we would be hard-pressed to answer basic questions: How would
doubling the size of the matrices alter the running time?  What is the
biggest matrix we can handle?  Furthermore, a minor change in the
procedure or hardware would invalidate the answer.

On the other hand, each of the $n^2$ entries in the product matrix
takes about $n$ steps to compute.  So the running time is
\textit{roughly} $n^2 \cdot n = n^3$.  This answer is certainly less
precise, but it was easy to derive and is easy to interpret.  For
example, we can see that doubling the size of the matrices from $n
\times n$ to $2n \times 2n$ would increase the running time from about
$n^3$ to about $(2n)^3 = 8n^3$--- a factor of 8.  And, assuming a
computer performs billions of operations in a reasonable time (as
opposed to millions or trillions), the largest matrices we could
handle would be roughly $1000 \times 1000$.  Furthermore, this
approximate answer is independent of tiny implementation and hardware
details.  It remains valid even after you upgrade your computer.

So approximate answers are quite attractive.  And asymptotic notation
allows one to formulate vague statements like ``roughly $n^3$'' in a
very precise way.

\subsection{Six Funny-Lookin' Symbols}

Asymptotic notation involves six weird little symbols:
%
\begin{center}
\begin{tabular}{cccccc}
{\huge $O$} & {\huge $\Omega$} &
{\huge $\Theta$} & {\huge $o$} &
{\huge $\omega$} & {\huge $\sim$} \\
oh & omega & theta & little-oh & little-omega & tilde
\end{tabular}
\end{center}
%
We'll focus on $O$, which is the most widely used.  The others are
about equally popular, except for $\omega$, which is the Jar-Jar of
the lot.

Suppose that $f$ and $g$ are functions.  Then the statement
%
\[
f(x) = O(g(x))
\]
%
means that there exist constants $x_0$ and $c > 0$ such that
%
\[
|f(x)| \leq c \cdot g(x)
\]
%
for all $x > x_0$.  Now this definition is pretty hairy.  But what
it's trying to say, with all its cryptic little constants, is that
\textit{$f$ grows no faster than $g$}.  A bit more precisely, it says
that $f$ is at most a constant times greater than $g$, except maybe
for small values of $x$.  For example, here's a true statement:
%
\[
5x + 100 = O(x)
\]
%
This holds because the left side is only about 5 times larger than the
right.  Of course, for small values of $x$ (like $x = 1$) the left
side is many times larger than the right, but the definition of $O$ is
cleverly designed to sweep aside such inconvenient details.

Let's work carefully through a sequence of examples involving $O$ in
order to better understand this definition.

\begin{claim}
$5x + 100 = O(x)$
\end{claim}

\begin{proof}
We must show that there exist constants $x_0$ and $c > 0$ such that
$|5x+100| \leq c \cdot x$ for all $x > x_0$.  Let $c = 10$ and $x_0 =
20$ and note that:
%
\[
|5x+100| \leq 5x + 5x = 10x \hspace{0.5in} \text{for all $x > 20$}
\]
\end{proof}

Here's another claim that points out a very common error involving $O$
notation.

\begin{claim}
$x = O(x^2)$
\end{claim}

\begin{proof}
We must show that there exist constants $x_0$ and $c > 0$ such that
$|x| \leq c \cdot x^2$ for all $x > x_0$.  Let $c = 1$ and $x_0 = 1$
and note that
%
\[
|x| \leq 1 \cdot x^2 \hspace{0.5in} \text{for all $x > 1$}
\]
\end{proof}

Many people fail to realize that a statement of the form $f(x) =
O(g(x))$ only places an \textit{upper bound} on the growth of the
function $f$.  So, for example, you'll often hear people say things
like, ``I can't use an algorithm that runs in $O(x^2)$ steps because
that's too slow.''  People who say things like that are \textit{dumb}
and you should make fun of them until they cry.  Okay, maybe not.  But
they are incorrect; we just proved that a fast algorithm that requires
only $x$ steps also runs in time $O(x^2)$!  One properly expresses a
\textit{lower bound} using the $\Omega$ notation, which we'll come to
presently.

What about the reverse of the previous claim?  Is $x^2 = O(x)$?  On an
informal basis, this means $x^2$ grows no faster than $x$, which is
false.  Let's prove this formally.

\begin{claim}
$x^2 \neq O(x)$
\end{claim}

\begin{proof}
We argue by contradiction; suppose that there exist constants $x_0$
and $c$ such that:
%
\[
|x^2| \leq c \cdot x \hspace{0.5in} \text{for all $x > x_0$}
\]
%
Dividing both sides of the inequality by $x$ gives:
%
\[
x \leq c \hspace{0.5in} \text{for all $x > x_0$}
\]
%
But this is false when $x = 1 + \max(x_0, c)$.
\end{proof}

We can show that $x^2 \neq O(100x)$ by essentially the same argument;
intuitively, $x^2$ grows quadratically, while $100 x$ grows only
linearly.  Generally, changes in multiplicative constants do not
affect the validity of an assertion involving $O$.  However, constants
in exponentials can be critical:

\begin{claim}
\[
4^x \neq O(2^x)
\]
\end{claim}

\begin{proof}
We argue by contradiction; suppose that there exist constants $x_0$
and $c > 0$ such that:
%
\[
|4^x| \leq c \cdot 2^x \hspace{0.5in} \text{for all $x > x_0$}
\]
%
Dividing both sides by $2^x$ gives:
\[
2^x \leq c \hspace{0.5in} \text{for all $x > x_0$}
\]
%
But this is false when $x = 1 + \max(x_0, \log c)$.\end{proof}

\subsection{Asymptotic Notation and Limits}

The remaining symbols, $\Theta$, $\Omega$, $o$, $\omega$, and $\sim$,
all have definitions similar to $O$: ``There exist constants blah and
blah such that for all blah, such-and-such holds.''  This may prompt a
sense of deja vu: these definitions are all quite similar to the
definition of a \textit{limit}.  In fact, this similarity has a happy
consequence: all these symbols have simple, intuitive interpretations
in terms of limits.  These are summarized in the table below.

\begin{center}
\begin{tabular}{cccc}
\textbf{Notation} & \textbf{Intuition} & ${\displaystyle \mathbf{\lim_{x\to\infty}f/g}}$ & \textbf{Example} \\[2ex]
$f = O(g)$
    & $f$ grows no faster than $g$
    & $\neq \infty$
    & $4x+7=O(x^2)$ \\
$f = \Omega(g)$
    & $f$ grows at least as fast as $g$
    & $\neq 0$
    & $9x^2=\Omega(x)$ \\
$f = \Theta(g)$
    & $f$ and $g$ grow at about the same rate
    & $\neq 0,\infty$
    & $8x^2 + x = \Theta(x^2)$ \\
$f \sim g$
    & $f$ and $g$ grow at the same rate
    & $= 1$
    & $x^2 + \sqrt{x} \sim x^2$ \\
$f = o(g)$
    & $f$ grows slower than $g$
    & $= 0$
    & $1/n = o(1)$ \\
$f = \omega(g)$
    & $f$ grows faster than $g$
    & $ = \infty$
    & $n^2 = \omega(n)$
\end{tabular}
\end{center}

This summary of asymptotic notation is valid for essentially all
functions encountered in computer science.  However, in the rare case
when $\lim_{n\to\infty} f/g$ does not exist or is negative, one must
consult the formal, nit-picky definitions of these symbols.  These
definitions are provided in the notes for the recitation following
this lecture.

\subsection{Enter the Dark Side}

So when someone talks asymptotics, why should you reach for your light
saber?

Asymptotic notation is so widely used to analyze algorithm running
times that there is a temptation to ``design for the notation'' rather
than for true usefulness.  Remember that asymptotic notation conceals
some information about an algorithm's performance while highlighting
other aspects.  So when a researcher designs an algorithm, he or she
might make tradeoffs so that the \textit{revealed} part look good even
though the \textit{concealed} parts make the algorithm undesirable.

Indeed, there are some notable examples of algorithms where asymptotic
notation obscures Deathstar-sized problems.  For example, there is an
ingenious algorithm that multiplies two $n \times n$ matrices in
$O(n^{2.376})$ steps instead of the obvious $O(n^3)$.  However, the
$O$ symbol conceals a constant so enormous that the naive
multiplication algorithm is preferable up to at least $n = 10^{20}$.
No one seems to have figured out exactly where the crossover point is,
but we're unlikely to come anywhere near it in this century at least.
Another example involves an algorithm that finds an approximate
solution to the \textit{Traveling Salesman Problem} in ``nearly linear
time''.  The running time to find an approximation within 10\% of
optimal is around $O(n \log^{400} n)$.  Now, in a sense, the author's
claim that this is ``nearly linear'' is correct; for example:
%
\[
n \log^{400} n = O(n^{1.01})
\]
%
But this is just a tad misleading since
%
\[
n \log^{400} n \gg n^{1.01}
\]
%
for all $n < 10^{100,000}$.  These extreme examples are well-known,
but whether misuse of asymptotic notation drives an wedge between
algorithmic theory and practice more generally is a question you might
ponder.  The moral is: use asymptotic notation to clarify, not
conceal.

Avoid the Dark Side, you must.
\end{document}
