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

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

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}
\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\arc}[2]{#1\!\longrightarrow\!#2}

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

\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{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}

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$ fall off.  In
order to find the best configuration of blocks, we'll need a fact from
physics about centers of mass.

\begin{fact}
If two objects have masses $m_1$ and $m_2$ and centers-of-mass at
positions $x_1$ and $x_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}

For this problem, only the horizonal dimension is relevant, and we'll
use the width of a block as our measure of distance.  Define the
\textit{offset} of a particular configuration of blocks to be the
horizonal distance from its center of mass to its rightmost edge.  The
offset measures how far the configuration can extend beyond the desk
since at best the center of mass lies right at the desk's 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}

We can find 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 great 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}\footnote{A different analysis was presented in lecture.}
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 $P(1)$ is true.

\noindent \textit{Inductive step:} For $n \geq 2$, 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 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}

\noindent Thus, by the physics fact, 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 greatest overhang achievable
with $n = 1$, 2, 3 and 4 blocks by computing 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}

We'll have to study harmonic sums more closely to determine what can
be done with large numbers of blocks.  Let's use integration to bound
the $n$-th harmonic number.  A picture is extremely helpful for
getting the right functions and limits of integration.

\begin{center}
\unitlength=0.4in
\begin{picture}(9.5,6)(-0.5,-1)
%\put(-0.5,-1){\framebox(9.5,6){}}
\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(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){}}
\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(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(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(4.5,0.3){\makebox(0,0){$y = 1/(x + 1)$}}
\put(3,2.2){\makebox(0,0){$y = 1/x$}}
\end{picture}
\end{center}

We can not integrate the function $1/x$ starting from zero.  So, for
the upper bound on $H_n$ we'll take the first term explicitly ($1/1$)
and then upper bound the remaining terms normally.  This gives:
%
\[
\begin{array}{rcccl}
{\displaystyle \int_0^n \frac{1}{x + 1} \ dx}
& \leq &
H_n
& \leq &
{\displaystyle 1 + \int_1^n \frac{1}{x} \ dx} \\
\\
{\displaystyle \Bigl. \ln(x + 1)\ \Bigr|_0^n }
& \leq &
H_n
& \leq &
{\displaystyle 1 + \Bigl( \Bigl. \ln x\ \Bigr|_1^n \Bigr)} \\
\\
\ln(n + 1)
& \leq &
H_n
& \leq &
1 + \ln n
\end{array}
\]
%
There are good bounds; the difference between the upper and lower
values is never more than 1.

Suppose we had a \textit{million} blocks.  Then the overhang we could
achieve--- assuming no breeze or deformation of the blocks--- would be
$\frac{1}{2} H_{1000000}$.  According to our bounds, this is:
%
\begin{align*}
\text{at least} \qquad &\frac{1}{2} \ln(1000001) = 6.907\ldots \\
\\
\text{at most} \qquad & \frac{1}{2} (1 + \ln(1000000)) = 7.407\ldots
\end{align*}
%
So the top block would extend about 7 lengths past the end of the
table!  In fact, since the lower bound or $\frac{1}{2} \ln(n + 1)$
grows arbitrarily large, there is \textit{no limit} on how far the
stack can overhang!

Mathematicians have worked out some extremely precise approximations
for the $n$-th harmonic number.  For example:
%
\[
H_n = \ln(n) + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon(n)}{120n^4}
\]
%
where $\gamma = 0.577215664\ldots$ is \term{Euler's constant} and
$\epsilon(n)$ is between 0 and 1.  Interestingly, no knows whether
Euler's constant is rational or irrational.

\section{Products}

We've now looked at many techniques for coping with sums, but no
methods for dealing with products.  Fortunately, we don't need to
develop an entirely new set of tools.  Instead, we can first convert
any product into a sum by taking a logarithm:
%
\[
\ln\left( \prod f(n) \right) = \sum \ln f(n)
\]
%
Then we can apply our summing tools and exponentiate at the end to
undo the logarithm.

Let's apply this strategy to a product that you'll encounter almost
daily hereafter:
%
\[
n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n
\]
%
First, we take a logarithm:
%
\[
\ln n! = \ln 1 + \ln 2 + \ln 3 + \ldots + \ln n
\]
This sum is rather nasty, but we can still get bounds by integrating.
First, we work out appropriate functions and limits of integration
with a picture.

\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 Now we integrate to get bounds on $\ln n!$.
%
\[
\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 \Bigl|_1^n}
& \leq &
\ln n!
& \leq &
{\displaystyle \Bigl. (x+1) \ln(x+1) - (x+1) \Bigl|_1^n}
\\
n \ln n - n
& \leq &
\ln n!
& \leq &
(n + 1) \ln(n+1) - n
\end{array}
\]
%
Finally, we exponentiate to get bounds on $n!$.
%
\[
\begin{array}{rcccl}
{\displaystyle \frac{n^n}{e^n}}
& \leq & n! & \leq &
{\displaystyle \frac{(n+1)^{(n+1)}}{e^n}}
\end{array}
\]

This gives some indication how big $n!$ is: about $(n/e)^n$.  This
estimate is often good enough.  However, as with the harmonic numbers,
more precise bounds are known.

\begin{fact}
\[
\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)}
\]
\end{fact}

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!  Taken together, these bounds imply \term{Stirling's
Formula}:
%
\[
n! \sim \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; the expression on the right is your
true 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$?

\section{Asymptotic Notation}

Approximation is a powerful tool.  It lets you sweep aside irrelevant
detail without losing track of the big picture.

Approximations are particularly useful in the analysis of computer
systems and algorithms. For example, suppose you wanted to know how
long multiplying two $n \times n$ matrices takes.  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.

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 proportional
to $n^3$.  This answer is certainly less precise.  However,
high-precision answers are rarely needed in practice.  And this
approximate answer is independent of tiny implementation and hardware
details; it remains valid even after you upgrade your computer.

Computer scientists make heavy use of a specialized \term{asymptotic
notation} to describe the growth of functions approximately.  The
notation involves six weird little symbols.  We've already encountered
one:
%
\[
f(n) \sim g(n) \hspace{0.5in}
\text{means} \hspace{0.5in}
\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1
\]
%
Less formally, $f \sim g$ means that the functions $f$ and $g$ grow at
essentially the same rate.  We've already derived two important
examples:
%
\[
H_n \sim \ln n \hspace{1in} n! \sim \sqrt{2 \pi n} \left( \frac{n}{e}\right)^n
\]

Here are the other five symbols in the asymptotic notation system:

\begin{center}
\begin{tabular}{ccccc}
{\huge $O$} & {\huge $\Omega$} & {\huge $\Theta$} & {\huge $o$} & {\huge $\omega$} \\
oh & omega & theta & little-oh & little-omega
\end{tabular}
\end{center}

We'll focus on the most important one, $O$.  Here's the definition:
given functions $f, g : \mathbb{R} \to \mathbb{R}$, we say that
%
\[
f(x) = O(g(x))
\]
%
if there exist constants $x_0$ and $c > 0$ such that $|f(x)| \leq c
\cdot g(x)$ for all $x \geq x_0$.  Now this definition is pretty
hairy.  But what it's trying to say, with all its cryptic little
constants, is that $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:
%
\[
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 such inconvenient details under the rug.

Let's work through a sequence of examples carefully to better
understand the 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 \geq 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 \geq 20$}
\]
\end{proof}

\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 \geq 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 \geq 1$}
\]
\end{proof}

What about the reverse?  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 \geq x_0$}
\]
%
Dividing both sides of the inequality by $x$ gives:
%
\[
x \leq c \hspace{0.5in} \text{for all $x \geq x_0$}
\]
%
But this is false when $x = \max(x_0, c + 1)$.
\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 are 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 \geq x_0$}
\]
%
Dividing both sides by $2^x$ gives:
\[
2^x \leq c \hspace{0.5in} \text{for all $x \geq x_0$}
\]
%
But this is false when $x = \max(x_0, 1 + \log c)$.
\end{proof}

While asymptotic notation is useful for sweeping aside irrelevant
detail, it can be abused.  For example, there are ingenious algorithms
for multiplying matrices that are asymptotically faster than the naive
algorithm.  The ``best'' requires only $O(n^{2.376})$ steps.  However
interesting theoretically, these algorithms are useless in practice
because the constants hidden by the $O$ notation are gigantic!

\vspace{1in}

\noindent \textit{For more information about asymptotic notation see
the ``Asymptotic Cheat Sheet''.}
\end{document}
