\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}
\usepackage{graphics}

\textwidth=6.5in
%\topmargin=-.15in
%\evensidemargin=0.75in
%\oddsidemargin=0.7pt
%\newcommand {\pindent} {\hspace*{20pt}}
\textheight=9.5in
\parskip=12pt plus 2pt minus 2pt
\pagestyle{empty}
\setlength{\parindent}{0in}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill
L12$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}}
\newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}}
%\newcommand{\remove}[1]{}

\begin{document}

\renewcommand{\thepage}{\arabic{page}}


\Huge
\pagetitle{Lecture Overview}
Finding Summation Formulas\\
\\
Double Sums\\
\\
Computing Products: Estimating \protect{$n!$}\\
\\
Asymptotic Notation\\

\pagetitle{Finding Summation Formulas}
What is the source of the simple formula?\\
\\
$\sum_{i=1}^n i = \frac{n(n+1)}{2}$\\

and the source of:
\begin{eqnarray*}
\sum_{i=1}^n i^2 & = & \frac{(2n+1)(n+1)n}{6} \\
                 & = & \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \\
                 & \sim & \frac{n^3}{3}
\end{eqnarray*}

Integral method:
\begin{eqnarray*}
\int_0^n x^2 \ dx \leq \sum_{i=1}^n i^2 \leq \int_0^n (x+1)^2 \ dx \\
\frac{n^3}{3} \leq \sum_{i=1}^n i^2 \leq \frac{(n+1)^3}{3} - \frac{1}{3}
\end{eqnarray*}

\pagetitle{Finding Summation Formulas,\\ Cont.}
So, \\
$\sum_{i=1}^n i^2 \sim \frac{n^3}{3}$

To get exact formula try:\\
$\sum_{i=1}^n i^2 = an^3 + bn^2 + cn + d$

Then try to plug enough values:\\
\begin{eqnarray*}
n = 0 & \rightarrow & 0 = d \\
n = 1 & \rightarrow & 1 = a + b + c + d \\
n = 2 & \rightarrow & 5 = 8a + 4b + 2c + d \\
n = 3 & \rightarrow & 14 = 27a + 9b + 3c + d
\end{eqnarray*}

The solution is:\\
$a = 1/3, b = 1/2, c = 1/6, d = 0$.

Now we must prove that our guess \\
$n^3/3 + n^2/2 + n/6$\\
is correct.

\pagetitle{Double Sums}

Sums of sums,

Evaluate the inner sum, replace with a closed form and the
the outer sum.

Exchanging the order of summation.

$\sum_{k=1}^n H_k = \sum_{k=1}^n \sum_{j=1}^k 1/j$

just to start:\\
$\sum_{k=1}^n H_k \approx \int_{k=1}^n \ln n \approx n\ln n-n.$

the pairs $(k,j)$ over which we are summing, form a triangle:
\[
\begin{array}{c|ccccccc}
 &j&1&2&3&4&\cdots&n\\
\hline
k\\
1&1\\
2 &1&1/2\\
3 &1&1/2&1/3\\
4 &1&1/2&1/3&1/4\\
 &\cdots\\
n &1&1/2&&\cdots&&&1/n
\end{array}
\]

\pagetitle{Double Sums, Cont.}

More convinient to sum the columns and then the row:

$\sum_{k=1}^n H_k = \sum_{k=1}^n \sum_{j=1}^k 1/j$\\
$~~~~~~~~~~~~~~= \sum_{j=1}^n \sum_{k=j}^n 1/j$\\
$~~~~~~~~~~~~~~= \sum_{j=1}^n 1/j \sum_{k=j}^n 1$\\
$~~~~~~~~~~~~~~= \sum_{j=1}^n \frac1j (n-j+1)$\\
$~~~~~~~~~~~~~~= \sum_{j=1}^n \frac{n-j+1}j$ \\
$~~~~~~~~~~~~~~= \sum_{j=1}^n \frac{n+1}j - \sum_{j=1}^n \frac{j}{j}$\\
$~~~~~~~~~~~~~~= (n+1)\sum_{j=1}^n \frac1j - \sum_{j=1}^n 1$\\
$~~~~~~~~~~~~~~= (n+1)H_n-n$

\pagetitle{Computing Products:\\  Estimating \protect{$n!$}}

Most common product is factorial:

$n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n = \prod_{i=1}^n i$

Convert to sum by logarithm
\begin{eqnarray*}
\ln n! & = & \ln(1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n) \\
       & = & \ln 1 + \ln 2 + \ln 3 + \ldots + \ln(n-1) + \ln n \\
       & = & \sum_{i=1}^n \ln i
\end{eqnarray*}

\pagetitle{Computing Products:\\  Estimating \protect{$n!$}}
Use integral method, recall $\int \ln x \ dx = x \ln x -x $
\begin{eqnarray*}
\int_1^n \ln x \ dx \leq & \sum_{i=1}^n \ln i & \leq \int_0^n \ln(x+1) \ dx \\
n \ln(\frac{n}{e}) + 1 \leq & \sum_{i=1}^n \ln i & \leq (n+1) \ln\left(\frac{n+1}{e}\right) + 1 \\
\left(\frac{n}{e}\right)^n e \leq & n! & \leq  \left(\frac{n+1}{e}\right)^{n+1} e
\end{eqnarray*}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/integral2.eps,height=2in}}
\end{figure}

$n!  \approx (\frac{n}{e})^n$.

\pagetitle{Computing Products:\\  Estimating \protect{$n!$}}
More careful calculation results in:
\begin{fact}[Stirling's Formula]
\[
\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}

Since $e^{1/(12n+1)}$ and $e^{1/12n}$ both approach 1 as 
$n$ grows large.
 

Bounds are tight e.g., :
\begin{eqnarray*}
100! & \geq & \sqrt{200 \pi} \left(\frac{100}{e}\right)^{100} e^{1/1201} \\
100! & \leq & \sqrt{200 \pi} \left(\frac{100}{e}\right)^{100} e^{1/1200}
\end{eqnarray*}

\pagetitle{Asymptotic Notation}

$f(n) \sim g(n)$ means 
$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} \rightarrow 1$.

\begin{eqnarray*}
H_n & = &\sum_{i=1}^n \frac{1}{i} \\
    & = & \ln n + \gamma + \frac{1}{2n} + \frac{1}{12n^2} +
          \frac{\epsilon(n)}{120n^4} \\
    & \sim & \ln n
\end{eqnarray*}

And,\\
$n! \sim \sqrt{2 \pi n} (\frac{n}{e})^n$.

\pagetitle{Asymptotic Notation}

5 symbols for asymptotic notation:

$O$ -- ``Oh'' or ``Big Oh''\\
$o$ -- ``Little Oh''\\
$\Theta$ -- ``Theta''\\
$\omega$ -- ``Little Omega''\\
$\Omega$ -- ``Omega''\\

\pagetitle{Big Oh}

Most frequently used, upper bound on the growth of a function\\
e.g., running time of an algorithm

\begin{defin*}
Given functions $f, g : {\cal R} \mapsto {\cal R}$, we say that $f(x)
= O(g(x))$ if there exists a constant $c > 0$ and an $x_0$ such that
for all $x \geq x_0$, $|f(x)| \leq c g(x)$.
\end{defin*}

$f(x) = O(g(x))$ means that $f$ grows no faster than $g$.\\
$f(x) = O(g(x))$ means $f(x) \leq g(x)$, except that we're willing 
to ignore a constant factor ($c$) and to allow exceptions for small 
$x$ (i.e., $x < x_0$).

Can express the idea $f(x) = O(g(x))$ by:\\
$f(x) \leq O(g(x))$, $f(x)$ is $O(g(x))$,\\
$f(x) \in O(g(x))$, 
or $f(x)$ ``is on the order of'' $g(x)$.  

\pagetitle{Big Oh, Cont.}
is $x = O(x^2)$? 

Theorem: If $f(x) = x$ and $g(x) = x^2$, then $f(x) = O(g(x))$.

Proof: We must prove that there exists a constant $c > 0$ and an $x_0$ such
that for all $x \geq x_0$, $|x| \leq c x^2$.  In particular, we can
choose $c = 1$ and $x_0 = 1$.  Then for all $x \geq 1$, $|x| \leq 1
\cdot x^2$.

$x^2 = O(x)$?\\
No --- $x^2$ grows faster than $x$ asymptotically.

Theorem: $x^2 \neq O(x)$

The proof is by contradiction.\\
Assume (aim contradiction) that $x^2 = O(x)$.\\
Then there exists a constant $c > 0$
and an $x_0$ such that for all $x \geq x_0$, $|x^2| \leq c x$.\\
This implies that for all $x \geq x_0$, $x \leq c$.\\
False for $x \geq \max(c + 1, x_0)$.

$x^2 = O(100x)$ is false as well.

\pagetitle{Big Oh, Cont.}

Theorem: $100x^2 = O(x^2)$

Proof: Choose $c = 100$ and $x_0 = 1$.  \\
Then for all $x \geq 1$, $|100x^2| \leq 100 x^2$\\

Theorem: $x^2 + 100x + 10 = O(x^2)$

Proof: Choose $c = 111$ and $x_0 = 1$.  \\
Then for all $x \geq 1$, $|x^2 + 100x + 10| \leq 111 x^2$.


\pagetitle{Big Oh, Cont.}

Generalize the preceding theorem to an arbitrary quadratic
polynomial.

Theorem: $a_1 x^2 + a_2 x + a_3 = O(x^2)$

Proof: Choose $c = |a_1| + |a_2| + |a_3|$ and $x_0 = 1$.\\
Then for all $x \geq 1$, $|a_1 x^2 + a_2 x + a_3| \leq (|a_1|
+ |a_2| + |a_3|) x^2$.\\

Intuitively, exponential functions grow faster than polynomials, even
very high degree polynomials.\\

Theorem: $x^{10} = O(e^x)$

Proof: Choose $c = 1$ and $x_0 = e^5$.\\
 It can be proven using calculus that
$10 \ln x \leq x$ for all $x \geq e^5$.  Exponentiating gives that for
all $x \geq e^5$, we have $e^{10 \ln x} \leq e^x$ or equivalently
$x^{10} \leq e^x$.

\pagetitle{Big Oh, Cont.}

Example an algorithm that multiply $n \times n$ 
matrices runs in cubic time --- $T(n) = O(n^3)$

(ignoring terms related to machine specific).

If $n$ doubles the runnimg time will increase by a factor
of about $8$ for large $n$.

Give indication for the scalability of an algorithm.

\pagetitle{Big Oh,\\ Exponential Fiasco}

is $4^x = O(2^x)$?

Theorem: $4^x \neq O(2^x)$

Proof is by contradiction.  Assume (aim contradiction)
that $4^x = O(2^x)$.\\
Then there exists a constant $c > 0$ and an $x_0$ 
such that for all $x \geq x_0$, $|4^x| \leq c2^x$.  
This implies that for all $x \geq x_0$, $2^x \leq c$.  \\
False for $x \geq \max(\ln(c + 1), x_0)$.

\pagetitle{Constant Confusion}

Every constant is $O(1)$.\\
For example, $17 = O(1)$.  This is true
$f(x) = 17$ and $g(x) = 1$,\\ 
$|f(x)| \leq c g(x)$ when
$c$ = 17 and $x_0 = 1$

We can prove that any constant is $O(1)$,\\
for all $n$, $n = O(1)$.

$n = O(1)$?

Do we refer to the function: $x$, $f(x) = n$\\
Then $n = O(1)$

Or to: $f(n) = n$\\
then $n \neq O(1)$.






\end{document}
