
\documentstyle[11pt,twoside,amstex,psfig]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}


\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{tut#1}{Notes for Recitation #1 (#2/98)}{#3}
}


%\newcommand{\emph}[1]{{\em #1}}
\renewcommand{\naturals}{N}
\renewcommand{\reals}{R}
%\newcommand{\textbf}[1]{{\bf #1}}

\newtheorem{falsethm}{False Theorem}

\begin{document}

\recn{5}{10/9}{October 9, 1998}

\iffalse
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi

\section{Asymptotic Notations}

In many parts of mathematics and computer science, 
one needs to compare growth rates of functions.
There are about $6$ ways to make such comparisons.

\subsection{Basic asymptotic relations}

The most common notations are $O()$, $\Theta()$, and $\Omega()$:

\begin{defin}
For functions $f,g:\reals \to \reals$,  define
\[f=O(g) \mbox{  iff  } \exists c>0 \exists x_0 \forall x \geq x_0: |f(x)| \leq
cg(x).\]
Also
\[f=\Theta(g) \mbox{  iff  } [f=O(g) \mbox{ and } g = O(f)],\]
and
\[f=\Omega(g) \mbox{  iff  } g = O(f).\]
\end{defin}

The value of these notations is that they highlight growth rate and allow
suppression of distracting factors and low-order terms.  For example, if
the running time of an algorithm is
\[T(n) = 10n^3 - 20n^2 + 1,\]
then
\[T(n) = \Theta(n^3).\]
$T(n)$ grows \emph{cubically}: it is bounded both above and below by
functions of the form $c n^3$.

Another such example is
\[{{\pi^23^{x-7} + {(2.7x^{113} + x^9- 86)^4 \over \sqrt{x}} - 1.08^{3x}}} =
\Theta(3^x).\]

\begin{lemma}\label{abO}
If $f = O(g)$, then $af = O(bg)$ for any $a,b>0$
\end{lemma}

\emph{Exercise}: Prove Lemma~\ref{abO}.
\medskip

If $l(x)$ is any function which increases unboundedly --- $\ln x$ is a
good example --- then $x/{l(x)} < x$ as soon as $x$ gets large enough that
$l(x) > 1$.  In particular, $x/{l(x)} = O(x)$.  Intuitively, $f = O(g)$
means that, to within a constant factor, $g$ grows at least as fast as
$f$.  In this case, the $g$ grows strictly faster:

\newpage
\begin{theorem}\label{xlnx}
\[\mbox{It is not true that } x = O(x/\ln x).\]
\end{theorem}

\begin{proof}
We must show that for all $c > 0$, there does not exist an $x_0$
such that for all $x \geq x_0$, we have $|x| \leq c x/\ln x$.  But
$x > c x/\ln x$ for all $x > e^c$, so there can't be such an $x_0$.
\end{proof}

Notice that, again, the only fact we used about $\ln x$ in the above proof
is that it is an unbounded increasing function.

\subsection{Growth rates of common functions}

A more significant fact about the growth of $\ln x$ is
\begin{theorem}\label{lno}
\[\forall a > 0: \ln x = O(x^a).\]
\end{theorem}

\begin{proof}
Remember L'H$\hat{\mbox{o}}$pital's rule:  if $\mbox{Lim}_{x\rightarrow \infty}
f(x) = \infty = \mbox{Lim}_{x\rightarrow \infty} g(x)$, then
\[\mbox{Lim}_{x\rightarrow \infty} {f(x) / g(x)} = \mbox{Lim}_{x\rightarrow \infty}
{f'(x)/ g'(x)}\]
where $f',g'$ are the derivatives of $f,g$, and $f, g, f', g'$ are
continuous.
So
\[\mbox{Lim}_{x\rightarrow \infty} {\ln x \over x^a} =  
\mbox{Lim}_{x\rightarrow \infty} {{1/x} \over {a x^{a-1}}} = \mbox{Lim}_{x\rightarrow
\infty} {1 \over {a x^a}} = 0.\] The last equality follow from the
familiar fact -- which we'll take for granted -- that that for all $a>0$,
the value of $x^a$ grows unboundedly as $x$ approaches infinity.  Since
the limit is 0, we can be sure that once $x$ is large enough, $\ln x/x^a
\leq 1$, that is $\ln x \leq x^a$.  So indeed $\ln x = O(x^a)$.
\end{proof}

Similarly,
\begin{theorem}\label{expo}
\[\forall a >1: x = O(a^x).\]
\end{theorem}
\begin{proof}
We know that $\ln a > 0$, so in the Taylor series
\[a^x = a^0 + x (\ln a)a^0 + x^2 (\ln a)^2a^0/2 + \dots\]
all the coefficients are positive.  Hence
\[a^x > 1 + (\ln a)x > (\ln a)x \mbox{ for }x>0.\]
\end{proof}

\begin{corollary}\label{expk}
\[\forall k\in \naturals, a >1: y^k = O(a^y).\]
\end{corollary}
\begin{proof}
By induction on $k$.  In the base case $k=0$, we have $y^k = y^0 = 1 < a
\leq a^y$ for $y\geq 1$, so $y^0 = O(a^y)$.  Notice that the only facts we
have used here about $a^y$ are that $a^1 = a$ and $a^y$ is a nondecreasing
function of $y$.

We now assume the induction hypothesis $y^k = O(b^y)$ for all $b>1$ and
prove $y^{k+1} = O(a^y)$ for all $a>1$.  For any $a > 1$, let
$b=\sqrt{a}$, so also $b > 1$.  By hypothesis, $y^k
\leq cb^y$ for some $c>0$ and all $y \geq$ some $y_0$.  Also, by
Theorem~\ref{expo}, $y \leq c'b^y$ for some $c'>0$ and all $y \geq$ some
$y'_0$.  So 
\[\begin{array}{lclclcl}
y^{k+1}& = & y(y^k) & \leq & c'b^y(cb^y) & = & cc'(b^y)^2\\
& = & cc'b^{2y} & = & cc'(b^2)^y & = & cc'a^y
\end{array}\]
for $y\geq \max(y_0, y'_0)$, which shows that $y^{k+1} = O(a^y)$.
\end{proof}

\subsection{A note on O notation}

Often one sees expressions like:
\[(1 + 1/x)^n = 1 + n/x + O(1/x^2).\]
The above expression really means that 
\[(1 + 1/x)^n - 1 - n/x = O(1/x^2).\]
That is, the error term in the approximation for $(1+1/x)^n$ is at most a
constant divided by $x^2$.

\subsection{Induction and asymptotic notation}

One has to be careful when combining inductive proofs with asymptotic
notation.  Here is an example of a wrong proof.  Recall that
$F_n$ denotes the $n$-th Fibonacci number.

\begin{falsethm}
$F_n = O(1)$
\end{falsethm}

{\em Proof. } The proof is by strong induction.  Let $P(n)$ be the
predicate that $F_n = O(1)$.  In the base case, $P(1)$ is true because
$F_1 = 1 = O(1)$.  In the inductive step, for $n \geq 1$ assume that
$F_1 = O(1), F_2 = O(1), \ldots, F_n = O(1)$ to prove that $F_{n+1} =
O(1)$.  There are two cases.  If $n = 1$, then $F_{n+1} = F_2 = 1 =
O(1)$.  If $n > 1$, then $F_{n+1} = F_n + F_{n-1} = O(1) + O(1) =
O(1).$ \qed

Where is the bug?!  The proof is actually correct; the problem is that
it is not a proof of the theorem!  What we actually proved is that
$\forall n: F_n = O(1)$.  It is in fact the case that $\forall n:
P(n)$ i.e. $\forall n: F_n = O(1)$ is true. This is because once we
fix $n$, i.e. within the quantifier, $F_n$ is just a specific number
such as $F_{100}$ or $F_{1000}$ etc. so it is a constant and hence we
can say it is $O(1)$. However, this does not imply the same about the
{\em function} $f(n) = F_n$ which is what we care about.

\subsection{Other asymptotic relations}

There are three other asymptotic notations in common use.  We include
them here for the record, but will not use them much this term. 

The tightest of the relationships between growth rates is
\emph{asymptotic equality}, $\sim$:
\begin{defin}
\[f \sim g \mbox{  iff  } \mbox{Lim}_{x\rightarrow \infty} {f(x) \over g(x)} = 1.\]
\end{defin}
This was the relation described in lecture for the Harmonic number
\[H_n \sim \ln n.\]

For example, $x + 1/x \sim x - \sqrt{x}$.  Note that if the values of $f$
and $g $ are nonegative, then $f \sim g \implies f = \Theta(g)$.

\emph{Exercise}:  Give an example of $f,g$ such that 
$f = \Theta(g)$ but \textbf{not} $f \sim g$.

To indicate that $g$ actually grows even faster than $f$, we can use
``Little Oh''notation:
\begin{defin}
$f = o(g) \mbox{  iff  } \forall c > 0 \exists x_0 \forall x \geq x_0: |f(x)|
\leq c g(x)$.
\end{defin}
This definition is a little hard to follow because of all the quantifiers.
For functions, $g$, which are nonnegative --- which is generally all we
care about in this context --- a clearer way to say $f=o(g)$ is:
\[\mbox{Lim}_{x\rightarrow \infty} {f(x) \over g(x)} = 0.\]

For example, the proof of Theorem~\ref{xlnx} above actually yielded 
the stronger result:

\begin{theorem}
\[{x\over {\ln x}} = o(x).\]
\end{theorem}

\begin{theorem}
\[\mbox{It is not true that }{x\over 100} = o(x).\]
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of contradiction
that $x/100 = o(x)$.  Then for all $c > 0$, there exists an
$x_0$ such that for all $x \geq x_0$, $|x/100| \leq c x$.  In
particular, if $c = 1/200$, there must exist an $x_0$ such
that for all $x \geq x_0$, $|x/100| \leq x/200$.
Since this statement is false for all positive $x$, we have reached a
contradiction.
\end{proof}

Another, rarely used, asymptotic notation is ``Little Omega'',
$\omega()$, which is just the opposite of ``Little Oh'', $o()$.

\begin{defin}
$g = \omega(f) \mbox{  iff  } f = o(g)$
\end{defin}

For example, $x^2 = \omega(x)$ since $x^2$ grows strictly faster than
$x$.

\newpage
\section{Some Sums}

\subsection{Perturbation method}

We have seen some methods to find closed forms of sums.  Finding closed
form solutions is tricky business because it is not always the case that
they exist!  Let's carefully review the way to discover summation formulas
called the {\em perturbation} method in lecture.  As with all other
methods it only works sometimes.

\iffalse
Let $S_n = \sum_{i=0}^n a_i$. Then,
$$S_n + a_{n+1} = \sum_{i=0}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=1}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=0}^{n}a_{i+1}$$

How do we use this?
\fi

Consider the sum, $S_n = \sum_{i=0}^n ix^i$.

The general approach is to add the $(n+1)$st term to both sides,
\[
\begin{array}{lll}
S_n + (n+1)x^{n+1} &  = 0x^0 + \sum_{i=1}^{n+1}ix^i\\
& = \sum_{i=0}^{n}(i+1)x^{i+1}\\
& = \sum_{i=0}^{n}ix^{i+1} + \sum_{i=0}^{n}x^{i+1}\\
& = x\sum_{i=0}^n ix^i + x\sum_{i=0}^{n} x^{i}\\
& = xS_n + x(1-x^{n+1})/(1-x)
\end{array}
\]
Having found $S_n$ in the last expression, bring terms involving $S_n$ to
one side and solve,
\[(1-x)S_n = {{x(1-x^{n+1}) - (n+1)x^{n+1}(1-x)} \over (1-x)}\]
\[S_n= {{x-(n+1)x^{n+1}+nx^{n+2}} \over (1-x)^2}\]
 
\subsection{Integral method}

Let us now go back to the integral method and see how to evaluate the sum
$$\sum_{i=1}^{\infty} \frac{1}{i^2}$$
In a similar fashion to the example in the lecture,
this sum, minus its first term, is less than the area under the curve
$y = 1/x^2$ from $1$ to $\infty$.  That is,
\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2} & = & 1 + \sum_{i=2}^{\infty} 
\frac{1}{i^2} \\
& \leq & 1 + \int_1^{\infty} x^{-2} dx \\
& = & 2.
\end{eqnarray*}
Thus, our infinite sum is at most $2$, and in particular it converges.
In fact, one can prove (using complex analysis) that the exact value
of the sum is $\pi^2 / 6$; we won't prove this here.

\subsection{Formal manipulation}

Next let's look at the following {\em doubly infinite} sum
$$\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j,$$
where (critically) $$0 < x, y < 1.$$
We can therefore re-write this as
\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j & = &
\sum_{i=0}^{\infty} x^i \left( \sum_{j=0}^{\infty} y^j \right) \\
& = & \sum_{i=0}^{\infty} x^i \left( \frac{1}{1 - y} \right) \\
& = & \left( \frac{1}{1 - y} \right) \sum_{i=0}^{\infty} x^i \\
& = & \frac{1}{(1 - x) (1 - y)}.
\end{eqnarray*}

\subsection{And some you can't sum...}

We note that the manipulations above were justified because we had a
series of positive real numbers whose sum converged.
Just to reinforce this, here's a case in which re-arrangements
of the sum are clearly not allowed.
Let 
$$S = \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots.$$
Consider the following:
$$S = [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0.$$
$$S = 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.$$
What's the problem here?  

If we define $S_n = \sum_{i=0}^{n}(-1)^i$ then $S_n = 1$ for odd $n$
and $S_n = 0$ for even $n$. Hence $S_n$ does not have a well-defined
limit as $n$ tends to infinity.  $S$ is not a convergent sum.

\iffalse

\problem \textbf{(VARIANT OF F97.  COMMENTS PLEASE: SHOULD WE USE THIS?)}
Is a Harvard degree really worth more than an MIT degree?!  Let us say
that a person with a Harvard degree starts with \$40,000 and gets a
\$20,000 raise every year after graduation, whereas a person with an MIT
degree starts with \$30,000, but gets a 20\% raise every year.  Assume
inflation is a fixed $8\%$ every year.  That is, \$1.08 a year from now is
worth \$1.00 today.

\bparts

\ppart How much is a Harvard degree worth today if the holder will work
for $n$ years following graduation?

\ppart How much is an MIT degree worth in this case?

\ppart If you plan to retire after twenty years, which degree would
be worth more?

\eparts

\textbf{Solution to F97 problem}:

One dollar after year $i$ is worth $\frac{1}{(1+p)^i}$ in today's currency.

So $$H_n = \sum_{i=1}^{n} {10000i / (1+p)^i}$$
$$M_n = \sum_{i=1}^{n} {1000i^2 / (1+p)^i}$$
\begin{enumerate}
\item From lecture the sum 
$$\sum_{i=0}^{n} ix^i = 
{x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
So $$H_n = 10000({x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2})$$
for $x = 1/1.08$.

\item To calculate the sum $\sum_{i=0}^n i^2x^i$, let us
differentiate both sides of 
$$\sum_{i=0}^n ix^i = {x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
$$\sum_{i=0}^{n}i^2 x^{i-1} ={(1-x)^2(1-(n+1)^2x^n +n(n+2)x^{n+1}) +2(1-x)(x-(n+1)x^{n+1}+nx^{n+2}) \over (1-x)^4}$$
$$= {1 + x - (n+1)^2x^{n} + (2n^2+2n-1)x^{n+1} -n^2x^{n+2} \over (1-x)^3}$$
Multiplying both sides by $x$ we have:
$$\sum_{i=0}^{n}i^2 x^{i} = {x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3}$$ 

So $$M_n = 1000({x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3})$$


\item Take $x = 1/1.08$ and solve for $n$ such that $M_n \geq H_n$. We see that
$n = 17$ is a long enough wait for an MIT student to get ahead. After 
17 years, the MIT graduate has earned $M_{17} = \$674,680.28$ while the
Harvard graduate has earned only $H_{17} = \$657,099.62$.

\end{enumerate}
\fi

\newpage
\section{Akra-Bazzi and the Master Theorem}

\subsection{Applying Akra-Bazzi}

One difficulty in applying Akra-Bazzi is the problem of finding $p$.
This is hard because you have to solve the hard equation
$\Sigma_{i=1}^k a_i b_i^p = 1$.
You might approach this problem by guessing a value for $p$ and
computing the sum.
If the result is greater than $1$, then try a larger value of $p$; if
the result is smaller than $1$, try a smaller value.
However, you might be unlucky and never find the exact value.

Sometimes, computing $p$ is unnecessary.
Suppose that $g(x) = x^q$, where $q > p$.
Then $T(x)$ can be computed as follows:

\[\begin{array}{lcl}
T(x) & = & \Theta(x^p(1 + \int_1^x {u^q \over u^{p+1}} du)) \\
     & = & \Theta(x^p(1 + \int_1^x {u^{q-p-1}} du)) \\
     & = & \Theta(x^p(1 + {1 \over q-p}(x^{q-p} - 1) )).
\end{array}\]
Since $q > p$, the term $x^{q-p}$ dominates, so we get:
$$T(x) = \Theta(x^p x^{q-p}) = \Theta(x^q).$$
The solution does not depend on the hard-to-compute value $p$.
Thus, if $g(x) = x^q$, a good trick is to compute $\Sigma_{i=1}^k
a_i b_i^q$.  If the result is less than $1$, then we know $q > p$ and
so the solution is $\Theta(x^q)$.

For instance, for the recurrence $T(x) = T(x/3) + T(x/4) + x$,
we have $g(x) = x^1$, so $q = 1$.
Since $(1/3)^1 + (1/4)^1 < 1$, we know that $p < q$ and the solution
is $\Theta(x^q)$.

\subsection{The Master Theorem}

The ``Master Theorem'' is commonly used in discrete math and
algorithms courses.
See the presentation in the Cormen, Leiserson, Rivest book for 
6.046.
It can be used to solve many recurrences of the form:
\[T(n) = aT(\ceil{n/b}) + f(n)\]
where $T,f:\naturals\to \naturals, a > 0,$ and $b >1$.  Namely, let $\beta
= \log_b a$.  Then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^{\beta - \epsilon})
\mbox{ for some } \epsilon >  0,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Theta(f(n)) & \mbox{ if } af(n/b) \leq cf(n)
\mbox{ for some $c < 1$ and all large $n$.}
\end{array} \right.
\]

The third condition looks different, but it does not overlap with the
others, because if $af(n/b) \leq cf(n)$  for some $c < 1$ and all large
$n$, then
\[f = \Omega(n^{\beta + \epsilon})\]
for $\epsilon = - \log_b c$; note that $\epsilon > 0$ because $c < 1$.
(We leave the proof of this claim as an exercise.)  The converse, however,
does not hold, so we can't replace the stronger condition used in the
Master Theorem by this last condition.

\textbf{Solution to the Exercise}:

Assume for simplicity that $n$ is a power of~$b$, say $n = b^k$, and the
``smoothness'' condition $af(n/b) \leq cf(n)$ holds for all $n$.

So
\begin{align*}
    f(n) &\ge \left(a/c\right) f\left(n/b\right)
         \ge (a/c)
                \left((a/c)f((n/b)/b)\right)
         = (a/c)^2 f\left(n/b^2 \right)\\
        & = \cdots = (a/c)^k f\left(n/b^k\right)
         = \left(a/c\right)^k f(1).
\end{align*}

But
\begin{align*}
(a/c)^k & = (b^{\log_b a - \log_b c})^k
          = (b^k)^{(\log_b a - \log_b c)} \\
        & = n^{\log_b a - \log_b c},
\end{align*}
so
\[ f(n) = \Omega( \left(a/c\right)^k) = \Omega\left( n^{\log_b a - \log_b c} \right) = \Omega\left( n^{\log_b a + \epsilon} \right)
\]
where $\epsilon = - \log_b c$.
\medskip

The Master Theorem applies nicely to the common case when $f(n) =
\Theta(n^\alpha)$.

\begin{corollary}
If $T(n) = aT(\ceil{n/b}) + f(n)$ where $a > 0, b >1$ and $f(n) =
\Theta(n^\alpha)$, then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^{\beta}) & \mbox{ if } \alpha < \beta,\\
\Theta(n^\beta \log n) & \mbox{ if } \beta = \alpha, \\
\Theta(n^{\alpha}) & \mbox{ if } \alpha > \beta. \\
\end{array} \right.
\]
\end{corollary}

\begin{proof}

\noindent \textbf{Case 1}: $\beta > \alpha$.

Choose $\epsilon=\beta - \alpha > 0$.  We have that $\alpha = \beta -
\epsilon$; hence $f(n) =\Theta(n^\alpha) = \Theta(n^{\beta-\epsilon})$ with
$\epsilon > 0$.  So the first case of the Master Theorem applies, yielding
\[T(n)=\Theta(n^\beta),\]
as desired.

\noindent \textbf{Case 2}: $\beta = \alpha$.

Then $f(n) = \Theta(n^\beta),$ so the second case of the
Master Theorem applies, yielding
\[T(n)=\Theta(n^\beta \log n),\]
as desired.

\noindent \textbf{Case 3}: $\alpha > \beta$.

Let's prove this case first when $f(n) = dn^\alpha$ for some $d>0$ and all
large $n$.

Let $c = a/b^\alpha = b^\beta/b^\alpha = 1/b^{\alpha - \beta}$.  We know
$b>1$ and $\alpha - \beta>0$, so $b^{\alpha - \beta} > 1$.  Therefore $c =
1/b^{\alpha - \beta} < 1$.  Also,
\[af(n/b)  =  ad(n/b)^\alpha  = (a/b^\alpha)dn^\alpha = cf(n).\]
So the third case of the Master Theorem applies, yielding
\[T(n)= \Theta(f(n)) = \Theta(n^\alpha),\]
as desired.

Now suppose all we know is that $f(n) = \Theta(n^\alpha)$.  Then by
definition of $\Theta()$, there are constants $n_0,d_1,d_2>0$ such that
$d_1n^\alpha \leq f(n) \leq d_2n^\alpha$ for all $n > n_0$.  For $i=1,2$,
let $f_i(n) = f(n)$ for $n \leq n_0$, and for $n > n_0$, let $f_i(n) =
d_in^\alpha$.  So $f_1(n) \leq f(n) \leq f_2(n)$ for \emph{all} $n\in
\naturals$, and also $f_i(n) = d_in^\alpha$ for all $n>n_0$.

Now define $T_1,T_2$ by the conditions: $T_i(0) = T(0), T_i(1) = T(1)$,
and $T_i(n) = aT_i(\ceil{n/b}) + f_i(n)$ for $n>1$.  Since $f_i(n)$ equals
a constant times $n^\alpha$ for all large $n$, our earlier reasoning
shows that
\[T_i(n) = \Theta(n^\alpha)\]
for $i=1,2$.  But since $f_1(n) \leq f(n) \leq f_2(n)$
for all $n$, it follows (by an easy induction) that
\[T_1(n) \leq T(n) \leq T_2(n),\]
which immediately implies that $T(n) = \Theta(n^\alpha)$.

\end{proof}

It's helpful to note that the Master Theorem and its corollary still hold
if, instead of rounding $n/b$ up to $\ceil{n/b}$, we rounded down to
$\floor{n/b}$, or even chose to round up or down as a function of $n$.

\subsection{Master theorem example}

\iffalse

We saw in lecture a way to multiply two $n$ bit numbers by performing
three $n/2$-bit multiplications plus some fixed number of length~$n$
shifts and sums of $n$-bit numbers.  Each such addition or shift takes
$O(n)$ bit operations.  Thus if $T_1(n)$ is the number of bit
operations to multiply two $n$-bit numbers, we have
\[
    T_1(n) = 3 T_1\left( \left\lceil n/2 \right\rceil \right)
                + f(n)
\]
where $f(n) = O(n)$.

So $a = 3$, $b = 2$, $\log_b a > 1 + 0.58$.  Hence $f(n) = O(n^{\log_b
a - 0.58})$, and the first case of the Master Theorem applies, namely,
\[
    T_1(n) = \Theta(n^{\log_2 3}).
\]
This is much better than the $\Theta(n^2)$ operations that ordinary
gradeschool multiplication takes on some $n$-bit multiplications.
(This idea generalizes; two $n$-bit numbers can be multiplied with
$O(n \log n)$ bit operations.)

If $T_2(n)$ is the number of pairwise comparisons needed to sort $n$
numbers, then
\[
    T_2(n) = 2 T_2\left( \left\lceil n/2 \right\rceil \right)
                + f(n)
\]
where $n - 1 \le f(n) \le n + 1$.  So $a = 2$, $b = 2$, $\log_a b =
1$, $f(n) = \Theta(n) = \Theta(n^{\log_a b})$ and the second case of
the Master Theorem applies yielding
\[
    T_2(n) = \Theta(n \log n).
\]

\fi

Strassen, in 1972, discovered a way of multiplying two $n \times n$
matrices by performing only seven multiplications of linear
combinations of their eight $n/2 \times n/2$ submatrices and then
computing eight linear combinations of the seven product matrices.
Since a linear combination of a fixed number of $n/2 \times n/2$
matrices requires $O(n^2)$ arithmetic operations, the number,
$T_3(n)$, of arithmetic operations required by Strassen's procedure is
\[
    T_3(n) = 7 T_3 \left( \left\lceil n/2 \right\rceil \right)
                + O(n^2).
\]
The first case of the Master Theorem applies with $\log_b a =
\log_2 7 > 2$, so
\[
    T_3(n) = \Theta(n^{\log_2 7}) = O(n^{2.81}).
\]
This is a considerable improvement over the standard row-by-column
method of matrix multiplication, which takes $\Theta(n^3)$ operations.

Strassen's technique has been extended in various \emph{ad hoc} ways, now
it is actually known how to multiply $n \times n$ matrices with
$O(n^{2.49})$ operations.  However, no one believes the currently fastest
method is optimal.  It remains an open question whether $n \times n$
matrices can be multiplied in $\Theta(n^2)$ operations.

\subsection{Special case of the Master Theorem derived from Akra-Bazzi}

We show how an important special case of the Master Theorem can be
derived from Akra-Bazzi:

$$T(n) = aT(n/b) + n^{\alpha}$$ 
where $a > 0$ and $b >1$.
First we find $p$ such that $a(\frac{1}{b})^p=1$. 
In this case, $a = b^p$ or $p = \log_b a$. 

Then from the Akra-Bazzi theorem, 
$$T(n) = \theta(n^p(1+ \int_1^n {u^{\alpha} \over u^{p+1}} du))$$
$$= \theta(n^p(1+ \int_1^n u^{\alpha - p-1} du))$$
In the case when $\alpha \neq p$,
$$=  \theta(n^p(1+ \left[ {u^{\alpha - p} \over \alpha-p} \right]_1^n))$$
$$= \theta(n^p(1+ \frac{1}{\alpha-p} (n^{\alpha-p} -1))) = 
\theta((1-\frac{1}{\alpha-p})n^p+\frac{1}{\alpha-p}n^\alpha)$$
Assuming $a, b, \alpha$ are fixed constants (i.e., don't change with $n$),
$$ T(n) = \theta(n^p + n^{\alpha}) = \theta (n^{\log_b a} + n^{\alpha})$$
If $\alpha = p$,
then $$T(n) = \theta(n^p(1+ \int_1^n {1 \over u} du))$$
$$= \theta(n^p(1+ \ln n)) = \theta(n^{\alpha} \log n)$$
So all together we have,
$$
T(n) = \left\{ \begin{array}{ll}
\theta(n^{\log_b a}) & \mbox{ if } \log_b a > \alpha\\
\theta(n^{\alpha} \log n) & \mbox{ if } \log_b a = \alpha\\
\theta(n^{\alpha}) & \mbox{ if } \alpha > \log_b a
\end{array} \right.
$$

For some intuition on the Master Theorem, 
see Cormen, Leiserson, Rivest pages 65-67.
They break down $T(n)$ into some costs associated with nodes in a
tree.
In equation (4.6), then give two expressions, one for the total costs
associated with the leaves and one for the total costs associated with
the internal nodes.
Depending on the relative values of $a$ and $b$, one or the other of these
expressions can dominate, or then can give equal contributions.

\iffalse

\section{Direct proof of the Master Theorem}

We did not go over the proof in recitation.  The proof is here for the
record.

All the calculations in the proof are much simpler if we assume $n$ is a
power of $b \in \naturals$, so we can ignore the details of repeatedly
rounding real numbers to integers.  Of course in general, neither $b$ nor
any of it powers need be an integer.  Nevertheless, the conclusions we
reach below when powers of $b$ are integers can be shown to hold for
arbitrary real numbers. (We shall not give that argument here, \emph{cf}.\
Cormen, Leiserson, Rivest, \emph{Introduction to Algorithms}, McGraw-Hill,
1990, \S4.4.2.)

\begin{proof}
So assume $b,k \in \naturals, b,k\geq 1,$ and $n = b^k$.  Now we have,
\[\begin{array}{lcl}
T(n) & = & T(b^k) \quad = \quad aT(b^{k-1}) + f(b^k)\\
     & = & a(aT(b^{k-2}) + f(b^{k-1})) + f(b^k)\\ 
     & = & a^2T(b^{k-2}) + a^1f(b^{k-1})) + a^0f(b^k)\\ 
     & = & a^{k}T(1) + \sum_{i=0}^{k-1}a^if(b^{k-i}).
\end{array}\]
Since the argument above does not depend on the values of $f(j)$ for
$j<b$, there's no harm in assuming that $f(1) = T(1)$, so we can say
\[T(b^k) = \sum_{i=0}^k a^if(b^{k-i}).\]

Since the first term in the sum is $f(n)$ and all the terms are
nonnegative, this already tells us that
\[T(n) = \Omega(f(n)).\]

Since the last term is $a^k f(1)$ and $a = b^\beta$, we also have

\[T(n) \geq a^k f(1) = (b^\beta)^k f(1) = (b^k)^\beta f(1) = n^\beta f(1),\]
so
\[T(n) = \Omega(n^\beta).\]

If we can match either of these $\Omega()$ bounds on $T$ with $O()$
bounds, then we will have a $\Theta()$ bound.  So we now consider the
different cases for the behavior of $f$ and derive the needed $O()$
bounds.

\noindent \textbf{Case 1}: $f(n) = O(n^{\beta - \epsilon})$ for some
$\epsilon > 0$.

So
\[\begin{array}{lcl}
T(n) & = & T(b^k) \quad = \quad \sum_{i=0}^{k}a^if(b^{k-i})\\
     & = & O(\sum_{i=0}^{k}a^i(b^{k-i})^{\beta - \epsilon}).
\end{array}\]
Let $S(k)$ be this last sum, that is, $T(b^k) = O(S(k))$ where
\[S(k) ::= \sum_{i=0}^{k}a^i(b^{k-i})^{\beta - \epsilon}.\]
Let's focus on the $i$th term of $S(k)$.  Using the fact that $a = b^\beta$
and $b^k = n$,
\[\begin{array}{lclclcl}
a^i(b^{k-i})^{\beta - \epsilon} & = & (b^\beta)^i(b^{k-i})^{\beta -
       \epsilon} & = & b^{i \beta}b^{k\beta -i\beta - \epsilon(k - i)}\\
    & = & b^{k\beta -\epsilon(k - i)} & = & (b^k)^\beta/ (b^\epsilon)^{i-k}
    & = & n^\beta (1/b^\epsilon)^{k-i}.
\end{array}\]

So
\[\begin{array}{lclclcl}
S(k) & = & n^\beta \sum_{i=0}^{k}(1/b^\epsilon)^{k-i}\\
     & = & n^\beta \sum_{i=0}^{k}(1/b^\epsilon)^i\\
     & \leq & n^\beta \sum_{i=0}^{\infty}(1/b^\epsilon)^i\\
     & = & O(n^\beta)
\end{array}\]
The final $O()$ bound above follows because $b>1$, so $1/b^\epsilon <1$,
and therefore the infinite geometric series above is bounded by a
constant.  But since $T(n) = T(b^k) = O(S(k))$, we can conclude that
\[T(n) = O(n^\beta).\]
Since we already observed that $T(n) = \Omega(n^\beta)$, we have finally that
\[T(n) = \Theta(n^\beta)\]
as was claimed in this case.

\noindent \textbf{Case 2}: $f(n) = \Theta(n^\beta)$.

So
\[\begin{array}{lcl}
T(n) & = & T(b^k) \quad = \quad \sum_{i=0}^{k}a^if(b^{k-i})\\
     & = & \Theta(\sum_{i=0}^{k}a^i(b^{k-i})^\beta)\\
     & = & \Theta(\sum_{i=0}^{k}(b^\beta)^i(b^\beta)^{k-i})\\
     & = & \Theta(\sum_{i=0}^{k}b^{k \beta})\\
     & = & \Theta(\sum_{i=0}^{k}n^\beta) \quad = \quad \Theta(k n^\beta)
     \quad = \quad \Theta(n^\beta \log n).
\end{array}\]

\noindent \textbf{Case 3}: $af(n/b) \leq cf(n)$ for some $c < 1$ and all
large $n$.

So
\[\begin{array}{lclclcl}
f(n/b) & \leq & (c/a) f(n),\\
f(n/b^2) & \leq &  (c/a) f(n/b) & \leq & (c/a) ((c/a) f(n)) & = & (c/a)^2 f(n),\\
f(b^{k-i}) = f(n/b^i) & \leq  & (c/a)^i f(n),
\end{array}\]
providing $b^{k-i}$ is sufficiently large.  In particular, there is an $n_0>0$
such that the last inequality holds providing $b^{k-i}\geq n_0$.  So it holds
when $i \leq k - d$ where $d::= \log_b n_0$.
Therefore
\[\begin{array}{lcl}
T(n) & = & T(b^k) \quad = \quad \sum_{i=0}^{k}a^if(b^{k-i})\\
     & = & \sum_{i=0}^{k - d}a^i f(b^{k-i}) + \sum_{i={k-d+1}}^{k}a^if(b^{k-i})\\
     & \leq & \sum_{i=0}^{k - d}a^i (c/a)^i f(n) +
     \sum_{i=0}^{d-1}a^{k-i}f(b^i)\\
     & = & 
f(n) \sum_{i=0}^{k - d}c^i + a^k\sum_{i=0}^{d-1}a^{-i}f(b^i)\\
     & \leq &
f(n) \sum_{i=0}^{\infty}c^i + n^\beta\sum_{i=0}^{d-1}a^{-i}f(b^i).
\end{array}\]
But $c<1$, so the geometric series above is bounded by a constant, and the
final sum above does not depend on $n$.  This shows that
\[T(n) = O(f(n)) + O(n^\beta).\]
But we observed above that $f = \Omega(n^{\beta + \epsilon})$, so
\[T(n) = O(f(n)).\]

Since we also observed already that $T(n) = \Omega(f(n))$, we have finally
that
\[T(n) = \Theta(f(n))\]
as was claimed in this case.

\end{proof}

\fi
\iffalse

\section{Change of variable}

Another useful method to make a difficult looking recurrence easier is by a
change of variable.  This is similar to the change of variable
technique in calculus.  For example, consider the recurrence
\[T(n) = 2T(\floor{\sqrt{n}}) + \log n\]
with base condition $T(1) = 1$.  Here $T(n)$ is defined for all $n$.  Let
us first note that $T(n)$ is a nondecreasing function of $n$.

\begin{claim}
For all $n > 1$, $T(n) \geq T(n-1)$.
\end{claim}

{\em Proof. } 
By strong induction on $n$.

I.H.:  $P(n): T(n) \geq T(n-1)$.

Base:  $n=2$: $T(2) = 2T(\floor{\sqrt{2}}) + 1 = 2T(1) + 1 = 3 > 1 = T(1)$.

Ind. Step: Assume $P(k)$ is true for all $k \leq n$. We will prove that
$P(n+1)$ is true.  

$$T(n+1) = 2T(\lfloor \sqrt{n+1} \rfloor) + \log (n+1)$$
$$ \geq 2T(\lfloor \sqrt{n} \rfloor) + \log n$$
The latter is true because either $\lfloor \sqrt{n+1} \rfloor = \lfloor \sqrt{n} \rfloor$ 
or we can apply 
$P(\lfloor \sqrt{n+1} \rfloor)$ which says that  
$T(\lfloor \sqrt{n+1} \rfloor) \geq T(\lfloor \sqrt{n} \rfloor)$.
 
But then the right hand side is $T(n)$. So $T(n+1) \geq T(n)$. 
\qed

We will now solve the recurrence assuming $n$ is a power of $2$. 
First, make the substitution $n  = 2^m$. The recurrence becomes 
\[T(2^m) = 2 T(\floor{2^{m/2}}) + m \]

Now define $S(m) = T(2^m)$ for all integers $m \geq 0$.  Note that since
$T$ is nondecreasing, so is $S$.  Therefore, $S(m) = T(2^m) =
2T(\floor{2^{m/2}}) + m \leq 2T(2^{\ceil{m/2}}) + m = 2S(\ceil{m/2}) +
m.$

That is,
\[S(m) \leq 2S(\ceil{m/2}) + m.\]

Now to bound $S$, we define $S'(0) = S(0), S'(1) = S(1)$, and $S'(m) =
2S'(\ceil{m/2}) + m$ for $m>1$.  Now we can apply Case 2 of the Master
Corollary to get $S'(m) = \Theta(m \log m)$.  But $S(m) \leq S'(m)$ for
all $m$, so the $\Theta()$ bound on $S'$ becomes an $O()$ bound on $S$:
\[S(m) = O(m \log m).\]
Therefore, there is a $d>0$ such that $T(2^m) \leq d(m \log m)$ for all
large $m$.  Equivalently, $T(n) \leq d(\log n \log \log n)$ whenever $n$ is
a large power of two.  But $\log 2n = \Theta(\log n)$ and $T$ is
nondecreasing, so we can conclude that the bound of a constant times $\log
n \log \log n$ holds for even for $n$ \emph{between} powers of two.  In
other words,
\[T(n) = O(\log n \log \log n).\]

What about a lower bound? This can be derived in a similar fashion.
\[S(m) = T(2^m) =  2T(\floor{2^{m/2}}) + m \geq 2T(2^{\lfloor m/2 \rfloor}) + m
= 2S(\lfloor m/2 \rfloor) + m.\]
That is, $S(m) \geq 2S(\lfloor m/2 \rfloor) + m$.

This time define $S'(0) = S(0)$ and $S'(m) = 2S'(\floor{m/2}) + m$ for
$m>0$, so $S(m) \geq S'(m)$ for all $m$.
Now we can apply the Master Corollary to solve the recurrence for $S'$ to
get $S'(m) = \theta(m \log m)$, so
$S(m) = \Omega(m \log m)$.  By reasoning similar to that above for the
$O()$ bound, we conclude that
\[T(n) =  \Omega (\log n \log \log n).\]
Combining the upper and lower bounds, we have shown
\[T(n) = \Theta( \log n \log \log n).\]

The hard part in changing variables to solve recurrences is guessing what
substitution to make, but this is a skill that comes out of practice, just
as in calculus.

\fi

\newpage
\section{Team Problems}

\begin{problems}

\problem We begin with two large glasses.  The first glass contains a pint
of water, and the second contains a pint of wine.
We pour $1/3$ of a pint
from the first glass into the second, stir up the wine/water mixture in
the second glass, and then pour $1/3$ of a pint of the mix back into the
first glass.  We now repeat this pouring back-and-forth process a total of
$n$ times.
\bparts

\ppart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\ppart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\eparts

\emph{Solution}: The state of the system of glasses/wine/water at the
beginning of a round of pouring and pouring back is determined by the
total amount of wine in the first glass.  Initially, the first glass
contains one pint of water and no wine.  Suppose the first glass contains
$w$ pints of wine, $0\leq w \leq 1$.  Since we're at the beginning of a
round, it contains one pint of liquid, and therefore contains $1-w$ pints
of water.  The second glass contains the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pint of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints liquid and $1 - (2/3)w$ wine
in the second glass.  Pouring 1/3 pint back from second into first
transfers a proportion of (1/3)/(4/3) of the wine in the second glass into
the first.  So the round completes with both glasses containing a pint of
liquid, and the first glass containing
\[(2/3)w + (1/4)(1- (2/3)w) = 1/4 + w/2\]
pints of wine.  After the second round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after the $n$th round
\[
\begin{array}{lll}
w/2^n + \Sigma_{i=1}^n (1/2)^{i+1} &=  w/2^n + (1/2)\Sigma_{i=1}^n
(1/2)^{i}\\
& = w/2^n + (1/2)(-1 + \Sigma_{i=0}^n (1/2)^{i})\\
& = w/2^n + (1/2)(-1 + (1 - (1/2)^{n+1})/(1 - 1/2))\\
& = w/2^n - 1/2 + 1 - (1/2)^{n+1}\\
& = w/2^n + 1/2 - (1/2)^{n+1}.
\end{array}
\]
So when $w=0$ initially, the pints of wine in the first glass is
\[1/2 - (1/2)^{n+1}.\]
You would expect after a thorough mixing that the glasses would contain
the same amount of wine, viz. 1/2 pint.  Indeed, the limiting amount of
wine in the first glass approaches 1/2 from below as n approaches
infinity.  In fact, it approaches 1/2 no matter how the wine was initially
distributed.

\newpage
\problem
\bparts
\ppart Give an example of functions $f,g:\naturals\to\naturals$ such that
neither $f = O(g)$ nor $g = O(f)$.  Prove it.

\emph{Solution}: $f(n) = 1 + n(n \bmod 2), g(n) =1 + n ((1 + n) \bmod 2)$.
So $f(n)$ is $n$ times the size of $g(n)$ on odd $n$, vice-versa on even
$n$.

\ppart 
Prove or give a counterexample:
If $f_1,f_2,\dots$ is a sequence of functions from $\naturals$ to
$\naturals$ such that $f_i(n) = O(1)$ for all $i\geq 1$, then 
\[\sum_{i=1}^n f_i(n) = O(2^n).\]

\emph{Solution}: False, let $f_i$ be a constant function with $f(n) =
b(i)$ for all $n$, where $b(i)$ is nonnegative and not $O(2^i)$, for
example, $b(i) = i2^i$.  So $f_i = O(1)$ for each $i$.  Now
\[\sum_{i=1}^n f_i(n) \geq f_n(n) = b(n) \neq O(2^n).\]
\eparts

\newpage
\problem
\bparts
\ppart Show that the Master Theorem does not apply to
\[S(m) = S(m/2) + (\log m)^2.\]

\ppart Find a $\Theta()$ bound for $S$ anyway.

\ppart
Find a $\Theta()$ bound for
\[
T(n) = T(\sqrt{n}) + (\lg \lg n)^2.
\]
The base condition is $T(2)=1$.
\eparts

\textbf{Solution}:

(a) Use $a=1, b=2$, so $\beta = 0$, and $n^{\beta} = 1$. The first 
two cases of master theorem obviously don't apply since $f(n)$ grows
much faster than $\Theta (1)$. Now let's consider the third case.
(assume $\log m$ is base 2)

\[\begin{array}{lcl}
af(\frac{m}{b}) & \leq & cf(m) \\
f(\frac{m}{2}) & \leq & cf(m) \\
(\log \frac{m}{2})^2 & \leq & c(\log m)^2 \\
(\log m - 1)^2 & \leq & c(\log m)^2 \\
(\frac{\log m - 1}{\log m})^2 & \leq & c \\ 
\end{array}\]

For large n, $\frac{\log m -1}{\log m}$ becomes 1, so $c$ must be
greater than or equal to 1. Therefore, we can not use the third
case of master theorem since $c < 1$ does not exist.\\

(b) Assume $\log m$ is base 2.
\begin{eqnarray*}
S(m) &=& S(\frac{m}{2}) + (\log m)^2  \\
&=& (\log m)^2 + (\log \frac{m}{2})^2 + (\log \frac{m}{4})^2 \cdots (\log 2)^2 + S(1) \\
&=& \sum_{i=0}^{(\log m)-1} (\log \frac{m}{2^i})^2 + S(1) \\
&=& \sum_{i=0}^{(\log m)-1} (\log m - i)^2 + S(1) \\
&=& \sum_{i=1}^{\log m} i^2 + S(1) \\
&=& \frac{1}{6}\log m (\log m + 1) (2 \log m + 1) + 1 \\
\end{eqnarray*}

So, $S(m)$ is $\Theta((\log m)^3)$. \\

This also works with Akra-Bazzi.

(c) Substitute $n=2^m$ and note that $m=\log n$.
\[ T(2^m) = T(2^{\frac{m}{2}}) + (\log m)^2.\]
So let $S(m) = T(2^m)$.  Now,
\begin{eqnarray*}
T(n) = T(2^m) = S(m) &=& S(\frac{m}{2}) + (\log m)^2  \\
&=& \Theta ((\log m)^3) \\
&=& \Theta ((\log \log n)^3) \\
\end{eqnarray*}

So, $T(n)$ is $\Theta ((\log \log n)^3)$. 

\end{problems}
\end{document}
