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

\input{macros-course}

\begin{document}

\tutn{6}{3/12/99}{March 12, 1999 (revised 3/13 5pm)}

\section{Applying the Master Theorem}
In lecture we described a ``Master Theorem'' which 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$.  The Master Theorem
summarizes the result of repeatedly expanding the recurrence to obtain a
series and then noticing the pattern of the series.  We have referred to
this as ``plugging and chugging.''  Here is a version of the Master
Theorem which is slightly simpler than the one used in lecture.  We
postpone its proof to the Appendix.

\begin{theorem}[Divide-And-Conquer Master Theorem]
\label{master}
Let $\beta ::= \log_b a$.
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^\alpha)\mbox{ for some } \alpha < \beta,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Omega(f(n)) & \mbox{ if } f(n) = \Omega(n^\alpha) \mbox{ for some } \alpha > \beta.\\
\end{array} \right.
\]
\end{theorem}

An important feature to notice about this Master Theorem is that in the
first case we go from an $O()$ bound on $f$ to a tighter $\Theta()$ bound
on $T$.  The third case only gives an $\Omega()$ bound on $T$, which is a
trivial consequence of the recurrence.  Whenever the third case has come
up in practice so far, it has actually been true that $T=\Theta(f)$.  One
useful example of this is
\begin{corollary}\label{nbig}
If $f(n) = \Theta(n^\alpha)$ for $\alpha > \beta$, or if $f(n) =
\Theta(c^n)$ for some $c>1$, then
\[
T(n) = \Theta(f(n)).
\]
\end{corollary}
There are some nasty $f$'s, however, which prevent us from always having a
$\Theta()$ bound in the third case.

The proof of Corollary~\ref{nbig} is also in the Appendix.

It's helpful to note that the Divide-And-Conquer Master Theorem and
Corollary~\ref{nbig} 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 depending on the value of $n$.

\subsection{Examples}

\subsubsection{Fast integer multiplication}
There is a nice recursive procedure for multiplying the base two
representations of a pair of $n$ bit integers $a$ and $b$.  Assume $n$ is
even and let $a_0$ be the number represented by the $n/2$ low-order bits
of $a$, and $a_1$ be the number represented by the $n/2$ high-order bits.
Then $a = a_1 2^{n/2}+a_0$.  Similarly, let $b = b_1 2^{n/2}+b_0$.  Now,
multiply out:
\begin{eqnarray*}
a\cdot b & = & (a_1 2^{n/2}+a_0)(b_1 2^{n/2}+b_0)\\
 & = & a_0b_02^n + (a_0b_1 + a_1b_0)2^{n/2} + a_1b_1.
\end{eqnarray*} 
So we have reduced the $n$-bit multiplication to four $n/2$-bit
multiplications plus some additions of at most $n+1$-bit numbers and
multiplications by powers of $2^{n/2}$.  Now multiplication by a power of
two can be done by left-shifting base two representations.  So each of the
additions and shifts above takes $O(n)$ bit operations.  Thus if $T_0(n)$
is the number of bit operations to multiply two $n$-bit numbers, we have
\[
    T_0(n) = 4 T_0(\lceil n/2 \rceil )
                + f(n)
\]
where $f(n) = O(n)$.

Applying the Divide-And-Conquer Master Theorem to $T_0$, we have $a=4,
b=2, \beta = \log_b a=2> 1 =\alpha$, so the first case applies and $T_0(n)
= \Theta(n^\beta) = \Theta(n^2)$.  This is interesting, but really is no
more efficient than ordinary grade school multiplication of $n$-bit
numbers, which if you think about it, also takes $\Theta(n^2)$ operations
on bits.

But the behavior of divide-and-conquer recurrences gives us a hook to a
considerably more efficient way to multiply: if we could somehow reduce
the number of $n/2$-bit multiplications to three instead of four, even at
the cost of performing some large but fixed number of $n$-bit additions
and shifts, we will have a recurrence of the form
\[
    T_1(n) = 3 T_1(\lceil n/2 \rceil)
                + g(n)
\]
where $g(n) = O(n)$.

Now the Divide-And-Conquer Master Theorem applies with $a=3, b=2, \beta =
\log_2 3 = 1.58\pm0.01 > 1 =\alpha$, so the first case still applies, and
this time gives $T_1(n) = \Theta(n^\beta) = O(n^{1.59})$.  We have reduced
the exponent of the running time from 2 to 1.59, a dramatic, assymptotic
improvement!

So, how to do it with three $n/2$-bit multiplications?  Here they are:
\begin{eqnarray*}
p_1 & ::= & a_1b_1,\\
p_2 & ::= & a_0b_0,\\
p_3 & ::= & (a_1 +b_1)(a_0 + b_0).
\end{eqnarray*}
Now
\begin{eqnarray*}
a\cdot b & = & a_0b_02^n + (a_0b_1 + a_1b_0)2^{n/2} + a_1b_1\\
 & = & p_1 2^n + (p_3 - p_2 - p_1)2^{n/2} + p_2.
\end{eqnarray*} 

(This idea generalizes; two $n$-bit numbers can be multiplied with
$O(n \log n)$ bit operations.)

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

\subsubsection{Matrix Multiplication}
Generalizing the ingenious idea behind integer multiplication to matrices,
the German mathematician Strassen observed in 1972 that two $n \times n$
matrices could be multiplied by performing only \emph{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 (\lceil n/2 \rceil)
                + O(n^2).
\]
Again the first case of the Divide-And-Conquer Master Theorem applies with
$\log_b a = \log_2 7 = 2.8\pm0.01 > 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
$n \times n$ matrix multiplication is known to take $O(n^{2.4})$
operations.  No one believes the currently fastest method is optimal, but
it is unknown whether $n \times n$ matrix multiplication requires
$\Omega(n^{2 + \epsilon})$ operations for any positive $\epsilon$.

\subsection{Third case: when $f$ is big}
Suppose
\[
    T_4(n) = aT_4 (\lceil n/b \rceil) + c^n
\]
for $a>0$ and $b,c>1$.  Since $f(n) = c^n = \Omega(n^\alpha)$ for
\emph{any} $\alpha$, the third case of the Divide-And-Conquer Master
Theorem applies and we conclude only the obvious fact that
\[
T_4(n) = \Omega(c^n).
\]
However, Corollary~\ref{nbig} also applies and gives the tighter bound
$\Theta(c^n)$.

\subsection{A non-example}
The Master Theorem does not apply to
\[S(m) = S(m/2) + \log^2 m.\]

The reason is that here $a=1, b=2$, so $\beta = 0$, $n^{\beta} = 1$ and
$f(n) = \log^2 m$.  The first two cases of the Divide-And-Conquer Master
Theorem obviously don't apply since $f(n)\neq O(1)$, and the third case
does not apply because $f(n) = o(n^\epsilon)$ for all $\epsilon > 0$.

But we can still use the ``plug and chug'' technique to handle this
recurrence.  For definiteness, let's say $\log$ is the base 2 logarithm.

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

\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}}) + \ceil{\log n}\]
with base condition $T(1) = 1$.  This defines $T(n)$ for all $n$.

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$.  So
\[
S(m) = 2T(\floor{2^{m/2}}) + m = 2S(\floor{m/2}) + m,
\]
as long as $m$ is divisible by 2.  For simplicity, let's assume that we
can find an $f(m) =\Theta(m)$ such that for \emph{all} $m$
\[
S(m) = 2S(\floor{m/2}) + f(m).
\]
Now the Master Theorem applies, and we conclude
\[S(m) = \Theta(m \log m).\]

Therefore, there is are $c_1,c_2>0$ such that $c_1(m \log m) \leq T(2^m)
\leq c_2(m \log m)$ for all large $m$.  Equivalently,
\[c_1\log n \log \log n \leq T(n) \leq c_2\log n \log \log n
\]
whenever $n$ is a large power of two.

If these inequalities held for \emph{all} large
$n$, not just large powers of two, we could conclude that
\[
T(n) = \Theta(\log n \log \log n).
\]
Of course, in general the behavior of a function at all arguments cannot
be predicted from its behavior at some sparse set of arguments, so we
can't reliably justify this conclusion.  Also, we haven't justified the
assumption above that there was an $f(m) =\Theta(m)$.

\iffalse
The following exercise and example caused more confusion than
clarification.  Don't use it again. ARM 3/12/99

\textbf{Class Exercise}: Give an example of functions $t,f$ such that
$t(2^m) = f(m)$ for all $m$, but neither $t(n)$ nor $f(\floor{\log n})$ is
$O()$ the other.

\emph{Solution}: This is easiest to understand by drawing a picture, but
in lieu of that, here's a precise example:

Let
\[t(n) ::= \left\{ \begin{array}{ll}
n & \mbox{ if } n \mbox{ is a power of 2, else}\\
n^2 & \mbox{ if } \floor{\log n}\mbox{ is even, and}\\
0 & \mbox{otherwise}.
\end{array} \right.
\]
Let $f(m) ::= t(2^m) = 2^m$.  But for $2^{2k} < n < 2^{2k+1}$, we have
$t(n) = n^2$ and 
\[
f(\floor{\log n}) = t(2^{\floor{\log n}}) = 2^{\floor{\log n}} = O(n) = o(t(n)),
\]
so $t(n) \neq O(f(\floor{\log n})$.  Similarly,
for $2^{2k+1} < n < 2^{2k}$, we have
$t(n) = 0$ and $f(\floor{\log n})>0$ so $f(\floor{\log n}) \neq O(t(n))$.\\
\emph{End Solution.}
\fi

So all we can say is that this argument has led us to a \emph{plausible
guess} about a $\Theta()$ bound, namely, that $T(n) = \Theta(\log n \log
\log n)$.  If we're right (we are of course -- that's why we used this
example) we can use the guess to guide us to a proper proof.  For example,
we can now try to prove by induction that
\[
c_1\log n \log \log n \leq T(n) \leq c_2\log n \log \log n,
\]
for all $n> 2$.  Here $c_1,c_2>0$ must be positive constants which we
still have to determine, but we can often find what they are by trying the
induction proof and adjusting them to make the proof work.

\section{Team Problems}

\begin{problems}

\problem \textbf{Fast Medians.} The \emph{median} among $n$ ordered
elements is a ``middle'' element when they are sorted; it's unique if $n$
is odd and there are two medians if $n$ is even.  We've seen above that
merge-sorting $n$ elements takes $O(n \log n)$ comparisons.  Next week
we'll even show that sorting by any method whatsoever takes $\Omega(n \log
n)$ comparisons.  So according to the definition, it seems that $\Omega(n
\log n)$ comparisons would be needed to find the median among $n$
elements.  This was pretty much taken for granted until the 1970's when
Manuel Blum (a Professor at Berkeley a few years past his MIT Ph.D.)
discovered an astonishing, ingenious algorithm to find the median among
$n$ elements.

Blum begins by doing $\Theta(n)$ comparisons to select a certain subset of
$n/5$ elements, then recursively finding the median of these $n/5$.  This
initial median is then compared to \emph{all} the elements in a way which
determines a subset of at most $7n/10$ elements.  Blum then shows that
finding the true median is no more difficult than finding the median of
this last subset of $7n/10$ elements.

Let $M(n)$ be the number of comparisons needed by Blum's procedure.  The
description above is enough to obtain a recurrence equation for $M$.
State the recurrence and then derive a $\Theta()$ bound on $M$.

\textbf{Solution}:
\[
M(n) = M(n/5) + M(7n/10) + O(n).
\]

Given that we're trying to improve on $\Omega(n \log n)$, a good guess is
that $M(n) \leq cn$ for some $c>1$.  Derive $c$ by making it fit an
induction proof that $M(n) \leq cn$.  Once proved, this obviously implies
that $M(n)= \Theta(n)$.

\problem
\textbf{Life and Death.}
In ancient Mars, cannibalism was an essential way of life.  The Marons and
the Batons were two species that lived for several thousand years in close
contact.  Every year, first all the Marons sustained themselves by first
consuming Batons: two Marons ate one Baton between them.  Then they
reproduced: one-year-old Marons doubled in number while Marons that were
two or older tripled in number.  Then the surviving Batons consumed one
newborn Maron each, and then all the Batons reproduced to quadruple in
number.  This cycle repeated every year.  After 1 year there were two
1-year old Marons and two 1-year old Batons.  After 2 years there were two
1-year olds and two 2-year olds in each of the two species.  How many of
each will there be of each species at the end of $n$ years?  Try for an
exact closed form answer rather than just a $\Theta()$ bound.

\textbf{Solution}:
Let $g(n)$ be the number of Marons after $n$ years, and $f(n)$ the number
of Batons.

After $n-1$ years, we have $g(n-1)$ Marons and $f(n-1)$ Batons.  Then in
the $n^{th}$ year, from the rules of sustenance, the population of Batons
drops to $f(n-1) - (1/2)g(n-1)$, assuming the Maron population was even.
The number of 1-year old Marons is $g(n-1) - g(n-2)$, this time assuming
the population is nondecreasing, and their population doubles to $2(g(n-1)
-g(n-2))$.  Meanwhile the number of older Marons triples from $g(n-2)$ to
$3g(n-2)$.  Then it is the Batons turn.  The surviving Batons consume a
newborn Maron each.  So, assuming there are more newborn Marons than
surviving Batons, the population of Marons after $n$ years is
\begin{eqnarray*}
g(n) & = & 2(g(n-1)-g(n-2)) + 3g(n-2) -(f(n-1)-\frac{1}{2}g(n-1))\\
     & = & \frac{5}{2}g(n-1) + g(n-2) - f(n-1).
\end{eqnarray*}
The Batons then quadruple.  So the number of Batons after $n$ years is:
\[
f(n) = 4(f(n-1) - \frac{1}{2}g(n-1)).
\]

We know that $f(1) = g(1) = 2$ and $f(2) = g(2) = 4$.  Substituting these
values in the recurrences, we get $f(3) = g(3) = 8$ and $f(4) = g(4) =
16$.

We guess that $g(n) = f(n) = 2^n$.  We can verify this --- and the three
assumptions on which the validity of the recurrence rests --- by strong
{\em simultaneous} induction on the two populations.  That is, the
induction hypothesis requires properties of \emph{both} $f(n)$ and $g(n)$:

I.H. : $P(n): f(n) = g(n) = 2^n$.

Base:  $n=1$: $f(1) = g(1) = 2$, and $n=2$: $f(2) = g(2) = 4$. 

Ind. Step.: Assume $P(k)$ is true for $1 \leq n$.  To prove $P(n+1)$,
observe
\begin{eqnarray*}
f(n+1) & = & 4(f(n) - \frac{1}{2}g(n))\\
       & = & 4(2^n - 2^{n-1})\\
       & = & 4(2^{n-1}) = 2^{n+1}.\\
g(n+1) & = & \frac{5}{2}g(n)+g(n-1) - f(n)\\
       & = & \frac{5}{2}(2^{n}) + 2^{n-1} - 2^n\\
       & = & 2^{n+1}.
\end{eqnarray*}
\qed
\end{problems}

\newpage
\appendix
\section{The Technical Master Theorem}
The more general, but technical, form of the Master Theorem described in
lecture was
\begin{theorem}\label{lecmaster}
Suppose
\[
T(n) = aT(\ceil{n/b}) + f(n)
\]
where $T,f:\naturals\to \naturals, a > 0,$ and $b >1$. Let $\beta ::=
\log_b a$.  Then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^\alpha)\mbox{ for some } \alpha < \beta,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Theta(f(n)) & \mbox{ if } af(\ceil{n/b}) \leq cf(n)
\mbox{ for some $c < 1$ and all large $n$.}
\end{array} \right.
\]
\end{theorem}

Notice that Theorem~\ref{lecmaster} immediately implies the
Divide-And-Conquer Master Theorem~\ref{master}, because the first two
cases are the same in both Theorems and, as we noted, the third case of
Theorem~\ref{master} is trivial.

In Theorem~\ref{lecmaster} above, the technical, third condition looks
different from any we have used so far, but it yields a nontrivial,
$\Theta()$ bound on $T$.  As first step toward understanding how this
technical condition works, we observe that it does not overlap with the
first two conditions:
\begin{lemma}
If $af(\ceil{n/b}) \leq cf(n)$ for some $c < 1$ and all large $n$, then
\[f = \Omega(n^{\alpha})\mbox{ for some }\alpha > \beta.
\]
\end{lemma}

\begin{proof}
Assume for simplicity that $n$ is a power of~$b$, say $n = b^k$, and the
``smoothness'' condition $af(\ceil{n/b}) \leq cf(n)$ holds for all $n$.
So
\begin{align*}
    f(n) &\ge (a/c) f(n/b)
         \ge (a/c)
                ((a/c)f((n/b)/b))
         = (a/c)^2 f(n/b^2 )\\
        & = \cdots = (a/c)^k f(n/b^k)
         = (a/c)^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((a/c)^k) = \Omega( n^{\log_b a - \log_b c} ) = \Omega(n^{\log_b a + \epsilon})
\]
where $\epsilon = - \log_b c$.  Note that $\epsilon > 0$ because $c < 1$.
\medskip
\end{proof}

\begin{lemma}\label{gsmooth}
Suppose $\alpha > \beta$ and $g(n) = dn^\alpha$ for some $d>0$ and all
large $n$.  Then $g$ satisfies the smoothness condition.
\end{lemma}
\begin{proof}
\[
a\, g(n/b)=ad\,(\frac{n}{b})^\alpha=\frac{a}{b^\alpha}dn^\alpha=c\, g(n)
\]
where $c = a/b^\alpha$.  But $\alpha = \beta + \epsilon$, for
some $\epsilon >0$, so
\[c=
\frac{a}{b^{\beta + \epsilon}}=
\frac{a}{b^{\log_b a+ \epsilon}} =
\frac{a}{a b^\epsilon} = \frac{1}{b^\epsilon}.
\]
But $b>1$, so 
\[
c = 1/b^\epsilon < 1,
\]
as required.
\end{proof}

We can also use Theorem~\ref{lecmaster} to prove Corollary~\ref{nbig}.
Since, $T$ is always $\Omega(f)$, we need only show that $T =
O(f)$.

\textbf{Case 1}: $f(n) = \Theta(n^\alpha)$ for $\alpha > \beta$.
\begin{proof}
By hypothesis, $f(n) \leq dn^\alpha$ for some $d>0$ and all $n>n_0$.  Now
define $g(n)$ as follows: $g(n) ::= f(n)$ for $n\leq n_0$, and $g(n) =
dn^\alpha$ for $n>n_0$.  Also, define $S(n) ::= T(n)$ for $n \leq 1$ and
\[S(n) ::= aS(\ceil{n/b}) + g(n)\]
for $n>1$.  This uniquely defines $S$.  By the previous
Lemma~\ref{gsmooth}, $g$ satisfies the smoothness condition, so
Theorem~\ref{lecmaster} implies that $S(n) = O(g(n))$.  But we defined
$g$ so that $f \leq g$.  It follows by elementary induction that $T \leq
S$.  Hence, $T(n) \leq S(n) = O(g(n))$.  But by hypothesis, $g(n) \leq
d'f(n)$ for some $d'>0$, so $T=O(f)$.
\end{proof}

\textbf{Case 2}: $f(n) = \Theta(r^n)$ for some $r>1$.
\begin{proof}
In this case we can show that $f$ itself satisfies the smoothness
condition.  Then $T=\Theta(f)$ directly by Theorem~\ref{lecmaster}.

To verify smoothness, note that by hypothesis there is a $d>0$ such that
$f(n) \leq dr^n$ for all large $n$.  Now
\[
af(\ceil{n/b}) \leq adr^{\ceil{n/b}} \leq ad\, (r^{1/b})^{n+1}.
\]
But $r^{1/b} < r$ because $r$ and $b$ are $>1$.  Hence
\[
af(\ceil{n/b}) \leq ad\, (r^{1/b})^{n+1} =adr\, (r^{1/b})^n = o(r^n).
\]
So for any $\epsilon>0$ and large $n$, we conclude that
\[
af(\ceil{n/b}) \leq \epsilon r^n.
\]

Now by hypothesis we also have a $d'>0$ such that $d'r^n \leq f(n)$ for
all large $n$.  So letting $\epsilon = d'/2$,
\[
af(\ceil{n/b}) \leq \epsilon r^n = {d'r^n}/2 \leq f(n)/2,\]
proving that $f$ satisfies the smoothness condition with $c=1/2$.
\end{proof}

\subsection{Proof of the Technical Version}
All the plugging and chugging in the proof is 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.

\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.

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

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

\section{Exponentials and Logarithms}
Here is a review of the standard identities involving exponentials and
logarithms used throughout the previous proofs.  Let $a, b, c, x, y$ be
reals numbers, with $a,b,c$ positive.
\begin{eqnarray*}
a^{\log_a c} & = & c\\
\log_a(a^x) & = & x\\
a^{x+y} &=& a^x a^y\\
\log_a bc &=& \log_a b + \log_a c\\
\log_a(1/c) &= & - \log_a c\\
(a^x)^y & = & a^{xy}  =  (a^y)^x
\end{eqnarray*}

Now we have
\[
a^{\log_a c} = c = b^{\log_b c} = (a^{\log_a b})^{\log_b c}
= a^{(\log_a b)(\log_b c)}.
\]
Taking $\log_a$ of both sides of this equality yields
\[
\log_a c = (\log_a b)(\log_b c).
\]
Hence, for $a,b >1$ and any function $f(n)\geq 1$,
\[
\log_a f(n) = (\log_a b)\log_b f(n) = O(\log_b f(n)).
\]
That's why the base of the logarithm is unimportant in $O(\log f(n))$.

\end{document}
