%%  This is a LaTeX2e document.  On the toc system, you may have to
%%  process it with 'latex2e' instead of 'latex' if you are not using
%%  LaTeX2e as your default.

\documentclass[11pt]{article}

\usepackage{fullpage}

\setlength{\parindent}{0pt}

\setlength{\parskip}{11pt}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\theoremstyle{definition}

\newtheorem*{remark}{Remark}
\newtheorem*{definition}{Definition}
\newtheorem*{examples}{Examples}

\newcommand{\ceil}[1]{\lceil#1\rceil}

\newcommand{\hsmash}[1]{\rlap{$\displaystyle#1$}}

\begin{document}

\title{\bf Notes on Better Master Theorems\\
for Divide-and-Conquer Recurrences}

\author{Tom Leighton\\[\bigskipamount]
\em Mathematics Department and\\
\em Laboratory for Computer Science\\
\em Massachusetts Institute of Technology\\
\em Cambridge, Massachusetts 02139}

\date{October 9, 1996}

\maketitle

\begin{abstract}

Techniques for solving divide-and-conquer recurrences are routinely
taught to thousands of Computer Science students each year.  The
dominant approach to solving such recurrences is known as the Master
Method~\cite{clr}.  Recently, Akra and Bazzi~\cite{ab} discovered a
surprisingly elegant generalization of the Master Method that yields a
very simple formula for solving most divide-and-conquer recurrences.
In these notes, we provide a simple inductive proof of the Akra-Bazzi
result and we extend the result to handle variations of
divide-and-conquer recurrences that commonly arise in practice.

\end{abstract}

\section{Introduction}

Divide-and-conquer recurrences are ubiquitous in the analysis of
algorithms.  Many methods are known for solving recurrences such as
\[
    T(n) = \begin{cases}
                1                       & \text{if $n = 1$} \\
                2 T(\ceil{n/2}) + O(n)  &\text{if $n>1$},
            \end{cases}
\]
but perhaps the most widely taught approach is the Master Method that
is described in the seminal algorithms text by Cormen, Leiserson and
Rivest~\cite{clr}.

The Master Method is fairly powerful and results in a closed form
solution for divide-and-conquer recurrences with a special (but
commonly-occurring) form.  Recently Akra and Bazzi~\cite{ab}
discovered a far more general solution to divide-and-conquer
recurrences.  The Akra-Bazzi analysis is based on a special functional
transform that they call the ``order transform.''

In these notes, we give a simple inductive proof of the Akra-Bazzi
result that is suitable for use in an undergraduate algorithms or
discrete math class.  We also show that the Akra-Bazzi result holds
for a more general class of recurrences that commonly arise in
practice and that are often considered to be difficult to solve.

\section{The Akra-Bazzi Solution}

We begin with a simple inductive proof of the Akra-Bazzi result.  The
result holds for recurrences of the form:
\begin{equation}\label{eqnA}
    T(x) =
        \begin{cases}
            \Theta(1)   & \text{for $1 \le x \le x_0$} \\
            \sum_{i=1}^k a_i T(b_i x) + g(x)
                        & \text{for $x > x_0$}
        \end{cases}
\end{equation}
where\footnote{These conditions are somewhat less restrictive than
those of~\cite{ab}.}
\begin{enumerate}

\item
$x \ge 1$ is a real number,

\item
$x_0$ is a constant such that $x_0 \ge 1/b_i$ and $x_0 \ge 1/(1 -
b_i)$ for $1 \le i \le k$,

\item
$a_i > 0$ is a constant for $1 \le i \le k$,

\item
$b_i \in (0, 1)$ is a constant for $1 \le i \le k$,

\item
$k \ge 1$ is a constant, and

\item
$g(x)$ is a nonnegative function that satisfies the polynomial-growth
condition specified below.

\end{enumerate}

\begin{definition}

We say that $g(x)$ satisfies the \emph{polynomial-growth condition} if
there exist positive constants $c_1$, $c_2$ such that for all $x
\ge 1$, for all $1 \le i \le k$, and for all $u \in [b_i x, x]$,
\[
    c_1 g(x) \le g(u) \le c_2 g(x).
\]

\end{definition}

\begin{remark}

If $|g'(x)|$ is upper bounded by a polynomial in~$x$, then $g(x)$
satisfies the polynomial-growth condition.  For example, $g(x) =
x^\alpha \log^\beta x$ satisfies the polynomial-growth condition for
any constants $\alpha, \beta \in \mathbb{R}$.

\end{remark}

\begin{theorem}[\cite{ab}]

Given a recurrence of the form specified in Equation~\ref{eqnA}, let
$p$ be the unique real number for which $\sum_{i=1}^k a_i b_i^p = 1$.
Then
\[
    T(x) = \Theta\left(x^p \left(1 + \int^x_1 \frac{g(u)}{u^{p+1}}
                \,du \right)\right).
\]
\end{theorem}

\begin{examples}\leavevmode

\begin{itemize}

\item
If $T(x) = 2 T(x/4) + 3 T(x/6) + \Theta(x \log x)$, then $p = 1$ and
$T(x) = \Theta(x \log^2 x)$.

\item
If $T(x) = 2 T(x/2) + \frac{8}{9} T(3x/4) + \Theta(x^2/\log x)$, then
$p = 2$ and $T(x) = \Theta(x^2/\log \log x)$.

\item
If $T(x) = T(x/2) + \Theta(\log x)$, then $p = 0$ and $T(x) =
\Theta(\log^2 x)$.

\item
If $T(x) = \frac{1}{2} T(x/2) + \Theta(1/x)$, then $p = -1$ and $T(x)
= \Theta((\log x)/x)$.

\item
If $T(x) = 4 T(x/2) + \Theta(x)$, then $p = 2$ and $T(x) =
\Theta(x^2)$.

\end{itemize}

\end{examples}

The proof of Theorem~1 makes use of the following simple lemma from
calculus.

\begin{lemma}

If $g(x)$ is a nonnegative function that satisfies the
polynomial-growth condition, then there are positive constants $c_3$,
$c_4$ such that for $1 \le i \le k$ and all $x \ge 1$,
\[
    c_3 g(x)    \le x^p \int_{b_i x}^x \frac{g(u)}{u^{p+1}} \, du
                \le c_4 g(x).
\]

\begin{proof}

>From the polynomial-growth condition we know that
\begin{align*}
    x^p \int_{b_i x}^x \frac{g(u)}{u^{p+1}} \, du
        &\le x^p (x - b_i x)
            \frac{c_2 g(x)}{\min\{ (b_i x)^{p+1}, x^{p+1}\}}\\
%
        &= \frac{(1 - b_i) c_2}{\min\{1, b_i^{p+1}\}} \, g(x)\\
%
        &\le c_4 g(x)
\end{align*}
where we define $c_4$ to be a constant for which
\[
    c_4 \ge \frac{(1 - b_i) c_2}{\min\{1, b_i^{p+1}\}}
\]
for $1 \le i \le k$.

Similarly,
\begin{align*}
    x^p \int_{b_i x}^x \frac{g(u)}{u^{p+1}} \, du
        &\ge x^p (x - b_i x)
            \frac{c_1 g(x)}{\max\{ (b_i x)^{p+1}, x^{p+1}\}}\\
%
        &=   \frac{(1 - b_i) c_1}{\max\{1, b_i^{p+1}\}} \, g(x)\\
%
        &\ge c_3 g(x)
\end{align*}
where we define $c_3$ to be a constant for which
\[
    c_3 \le \frac{(1 - b_i) c_2}{\max\{1, b_i^{p+1}\}}
\]
for $1 \le i \le k$.
\end{proof}

\end{lemma}

We will use induction to prove Theorem~1, and so it will be helpful to
partition the domain of~$x$ into intervals $I_0 = [1, x_0]$ and $I_j =
(x_0 + j - 1, x_0 + j]$ for $j \ge 1$.

By the definition of~$x_0$, we know that if $x \in I_j$ for some $j
\ge 1$, then for $1 \le i \le k$, \ $b_i x \in I_{j'}$ for some $j' <
j$.  This is because
    $b_i x > b_i (x_0 + j - 1) \ge b_i x_0 \ge 1$,
and because
    $b_i x \le b_i (x_0 + j) \le x_0 + j - (1 - b_i) x_0 \le x_0 + j - 1$.
As a consequence, we know that the value of~$T$ in any interval after
$[1, x_0]$ depends only on the values of~$T$ in prior intervals.

\pagebreak

\begin{proof}[Proof of Theorem 1]

We first show that there is a positive constant~$c_5$ such that for
all $x > x_0$,
\[
    T(x) \ge
        c_5 x^p \left( 1 + \int_1^x \frac{g(u)}{u^{p + 1}} \, du \right).
\]
The proof is by induction on the interval~$I_j$ containing~$x$.  The
base case when $j = 0$ follows from the fact that $T(x) = \Theta(1)$
when $x \in [1, x_0]$ (provided that we choose~$c_5$ small enough).

The inductive  step is argued as follows:
\begingroup
\openup2\jot
\begin{alignat*}{-1}
    T(x)    &=   \sum_{i=1}^k a_i T(b_i x) + g(x) \\
%
            &\ge \sum_{i=1}^k a_i c_5 (b_i x)^p
                    \left(
                        1 + \int_1^{b_i x} \frac{g(u)}{u^{p+1}} \, du
                    \right)
                    + g(x)
                 &\quad& \text{(by induction)}
            \\
%
            &=   c_5 x^p \sum_{i=1}^k a_i b_i^p
                    \left(
                        1 + \int_1^x       \frac{g(u)}{u^{p+1}} \, du
                          - \int_{b_i x}^x \frac{g(u)}{u^{p+1}} \, du
                    \right)
                    + g(x)
            \\
%
            &\ge c_5 x^p \sum_{i=1}^k a_i b_i^p
                    \left(
                        1 + \int_1^x       \frac{g(u)}{u^{p+1}} \, du
                          - \frac{c_4}{x^p} \, g(x)
                    \right)
                    + g(x)
                && \text{(by Lemma 1)}
            \\
%
            &=   c_5 x^p
                    \left(
                        1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                          - \frac{c_4}{x^p} \, g(x)
                    \right)
                    + g(x)
            \\
%
            &=   c_5 x^p
                    \left(
                        1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                    \right)
                    + g(x) - c_5 c_4 g(x)
            \\
%
            &\ge c_5 x^p
                    \left(
                        1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                    \right)
\end{alignat*}
\endgroup
provided that $c_5 \le 1/c_4$.

The proof that there is a positive constant~$c_6$ such that for all $x >
x_0$,
\[
    T(x) \le c_6 x^p
            \left(
                1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
            \right)
\]
is nearly identical.  We need only insure that $c_6$ is chosen large
enough so that the base case is satisfied and so that $c_6 \ge 1/c_3$.
As a consequence, we can conclude that
\[
    T(x) = \Theta\left(x^p 
                \left(
                    1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                \right)
            \right),
\]
as claimed.
\end{proof}

\begin{remark}

If $g(x)$ grows faster than any polynomial in~$x$, then $T(x) =
\Theta(g(x))$.  Hence, Theorem~1 does not necessarily hold if $g(x)$
does not satisfy the polynomial-growth condition.

\end{remark}

\section{Variations}

Although the class of recurrences analyized in Section~2 is quite
broad, recurrences that arise in practice often differ in small ways
from the class specified in Equation~\ref{eqnA}.  For example, in
algorithm design, recurrences of the form
\[
    T(x) \le \sum_{i=1}^k a_i T(\ceil{b_i x}) + g(x)
\]
are common.

Generally speaking, the inclusion of floors and ceilings in a
recurrence does not significantly change the nature of the solution
(e.g., see \cite{ab,clr}), but the proofs of this fact tend to be
fairly tedious and specialized in nature.  In what follows, we
describe a general class of variations (which includes floors and
ceilings) and we show that the variations in this class do not affect
the solution of the recurrence (up to constant factors).  In
particular, we show that the solution of Theorem~1 holds for all
recurrences of the form:
\begin{equation}\label{eqnB}
    T(x) = \begin{cases}
                \Theta(1)   & \text{for $1 \le x \le x_0$} \\
                \sum_{i=1}^k a_i T(b_i x + h_i(x)) + g(x)
                            & \text{for $x > x_0$}
            \end{cases}
\end{equation}
where
\begin{enumerate}

\item
$x$, $x_0$, $a_i$, $b_i$, $k$, and $g(x)$ all satisfy the conditions
specified in Section~2,

\item
there is some constant $\epsilon > 0$ for which $|h_i(x)| \le
x/(\log^{1 + \epsilon} x)$ for $1 \le i \le k$ whenever $x \ge x_0$,

\item
there exist positive constants $c_1$ and $c_2$ such that for all $x
\ge 1$, for all $1 \le i \le k$, and for all $u \in [b_i x + h_i(x),
x]$,
\[
    c_1 g(x) \le g(u) \le c_2 g(x),
\]
and

\item
$x_0$ is chosen to be a large enough constant\footnote{Such a constant
value of~$x_0$ can be shown to exist using standard Taylor series
expansions and asymptotic analysis.} so that for any $i \le k$ and any
$x \ge x_0$,
\begin{enumerate}

\item
$\displaystyle
    \left(1 - \frac{1}{b_i \log^{1 + \epsilon} x}\right)^p
    \left(1 + \frac{1}
                   {\log^{\epsilon/2} \left(
                        b_i x + \frac{x}{\log^{1 + \epsilon} x}
                    \right)
                   }
    \right)
    \ge 1 + \frac{1}{\log^{\epsilon/2} x}
$,

\item
$\displaystyle
    \left(1 + \frac{1}{b_i \log^{1 + \epsilon} x}\right)^p
    \left(1 - \frac{1}
                   {\log^{\epsilon/2} \left(
                        b_i x + \frac{x}{\log^{1 + \epsilon} x}
                    \right)
                   }
    \right)
    \le 1 - \frac{1}{\log^{\epsilon/2} x}
$,

\item
$\displaystyle
    \frac{1}{2} \left( 1 + \frac{1}{\log^{\epsilon/2} x} \right) \le 1
$,

\item
$\displaystyle
    2 \left(1 - \frac{1}{\log^{\epsilon/2} x} \right) \ge 1
$.

\end{enumerate}

\end{enumerate}
For example, we might choose~$h_i$ so that
\[
    h_i(x) = \ceil{b_i x} - b_i x,
\]
thereby extending Theorem~1 to handle ceiling functions.  In this
case, $|h_i(x)| < 1$.  We can also use much larger functions, however.
For example, we could set $h_i(x) = -\sqrt{x}$ or $h_i(x) = x/(\log^2
x)$ for $x > 1$.

To analyze the more general recurrence, we will need the following
analogue of Lemma~1.

\begin{lemma}

There are positive constants $c_3$, $c_4$ such that for $1 \le i
\le k$ and all~$x \ge 1$,
\[
    c_3 g(x)
        \le x^p \int_{b_i x + h_i(x)}^x \frac{g(u)}{u^{p+1}} \, du
        \le c_4 g(x).
\]

\begin{proof}
The proof is identical to that for Lemma~1 except that we use
constraint~3 above in place of the polynomial-growth condition of
Section~2.
\end{proof}

\end{lemma}

\begin{theorem}

Given a recurrence of the form specified in Equation~\ref{eqnB}, let
$p$~be the unique real number for which $\sum_{i=1}^k a_i b_i^p = 1$.
Then
\[
    T(x) = \Theta\left(x^p
                \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
            \right).
\]

\begin{proof}

The proof is very similar to that of Theorem~1.  The main difference
is that we use a slightly stronger inductive hypothesis.  In
particular, we begin by showing that there is a positive
constant~$c_5$ such that for all $x > x_0$,
\[
    T(x) \ge c_5 x^p
             \left(1 + \frac{1}{\log^{\epsilon/2} x} \right)
             \left(1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right).
\]

The proof is by induction on the interval~$I_j$ containing~$x$.  The
base case when $j = 0$ follows from the fact that $T(x) = \Theta(1)$
when $x \in [1, x_0]$ (provided that $c_5$ is chosen to be a small
enough constant).  The inductive step is argued as follows:
\begingroup
\openup2\jot
\begin{alignat*}{-1}
T(x) &=   \sum_{i=1}^k a_i T(b_i x + h_i(x)) + g(x) \\
%
     &\ge \sum_{i=1}^k a_i c_5 (b_i x + h_i(x))^p
         \left(
             1 + \frac{1}{\log^{\epsilon/2} (b_i x + h_i(x))}
         \right)
     \\
     &\qquad\qquad\qquad \times
         \left(
             1 + \int_1^{b_i x + h_i(x)} \frac{g(u)}{u^{p+1}} \, du
         \right)
         + g(x)
     &\quad& \text{(by induction)}
     \\
%
     &\ge \sum_{i=1}^k a_i b_i^p c_5 x^p
        \left( 1 - \frac{1}{b_i \log^{1 + \epsilon} x} \right)^p
        \left( 1 + \frac{1}
                        {\log^{\epsilon/2}
                            \left(
                              b_i x + \frac{x}{\log^{1 + \epsilon} x}
                            \right)
                        }
        \right)
     \\
     &\qquad\qquad\qquad \times
        \left( 1 + \int_1               ^x \frac{g(u)}{u^{p+1}} \, du
                 - \int_{b_i x + h_i(x)}^x \frac{g(u)}{u^{p+1}} \, du
        \right)
         + g(x)
     && \text{(by the bounds on $h$)}
     \\
%
     &\ge \sum_{i=1}^k a_i b_i^p c_5 x^p
            \left(1 + \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                     - \frac{c_4}{x^p} \, g(x)
            \right)
             + g(x)
     \\
     &\qquad\qquad \text{(by constraint 4(a) on $x_0$ and Lemma 2)}
     \\
%
     &=   c_5 x^p
            \left( 1 + \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                     - \frac{c_4}{x^p} \, g(x)
            \right)
            + g(x)
    \\
%
     &=   c_5 x^p
            \left(1 + \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
            + g(x) - {}
            \hsmash{
                c_5 c_4 \left(1 + \frac{1}{\log^{\epsilon/2} x} \right) g(x)
            }
    \\
%
     &\ge c_5 x^p
            \left(1 + \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
\end{alignat*}
\endgroup
provided that $c_5 \le 1/(2 c_4)$ (by constraint~4(c) on~$x_0$).

The proof of the upper bound is quite similar.  In this case, we show
by induction that there is a positive constant~$c_6$ such that for all
$x > x_0$,
\[
    T(x) \le c_6 x^p
             \left( 1 - \frac{1}{\log^{\epsilon/2} x} \right)
             \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right).
\]
The base case is as before.  The inductive step is argued as follows:
\begingroup
\openup2\jot
\begin{alignat*}{-1}
T(x) &=   \sum_{i=1}^k a_i T(b_i x + h_i(x)) + g(x) \\
%
     &\le \sum_{i=1}^k a_i c_6 (b_i x + h_i(x))^p
        \left(
            1 - \frac{1}{\log^{\epsilon/2} (b_i x + h_i(x))}
        \right)
     \\
     &\qquad\qquad\qquad \times
        \left(
            1 + \int_1^{b_i x + h_i(x)} \frac{g(u)}{u^{p+1}} \, du    
        \right)
        + g(x)
     &\quad& \text{(by induction)}
     \\
%
     &\le \sum_{i=1}^k a_i b_i^p c_6 x^p
        \left( 1 + \frac{1}{b_i \log^{1 + \epsilon} x} \right)^p
        \left( 1 - \frac{1}
                        {\log^{\epsilon/2}
                            \left(
                              b_i x + \frac{x}{\log^{1 + \epsilon} x}
                            \right)
                        }
        \right)
     \\
     &\qquad\qquad\qquad \times
        \left( 1 + \int_1               ^x \frac{g(u)}{u^{p+1}} \, du
                 - \int_{b_i x + h_i(x)}^x \frac{g(u)}{u^{p+1}} \, du
        \right)
         + g(x)
     && \text{(by the bounds on $h$)}
     \\
%
     &\le \sum_{i=1}^k a_i b_i^p c_6 x^p
            \left( 1 - \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                     - \frac{c_3}{x^p} \, g(x)
            \right)
             + g(x)
     \\
     &\qquad\qquad \text{(by constraint 4(b) on $x_0$ and Lemma 2)}
     \\
%
     &=   c_6 x^p
            \left( 1 - \frac{1}{\log^{\epsilon/2} x}\right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du
                     - \frac{c_3}{x^p} \, g(x)
            \right)
            + g(x)
    \\
%
     &=   c_6 x^p
            \left( 1 - \frac{1}{\log^{\epsilon/2} x} \right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
            + g(x) - {}
            \hsmash{
                c_3 c_6 \left( 1 - \frac{1}{\log^{\epsilon/2} x} \right) g(x)
            }
    \\
%
     &\le c_6 x^p
            \left( 1 - \frac{1}{\log^{\epsilon/2} x} \right)
            \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
\end{alignat*}
\endgroup
provided that $c_6 \ge 2/c_3$ (by constraint~4(d) on~$x_0$).

Hence, we can conclude that
\[
    T(x)
        = \Theta\left(x^p
                \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} \, du \right)
            \right),
\]
as desired.
\end{proof}

\end{theorem}

\begin{remark}

It is worth noting that the $x/\log^{1 + \epsilon} x$ limit on the
size of~$|h_i(x)|$ is nearly tight, since the solution of the
recurrence
\[
    T(x) = \begin{cases}
                \Theta(1)       & \text{for $1 \le x \le x_0$} \\
                2 T\left(\frac{x}{2} + \frac{x}{\log x}\right)
                                & \text{for $x > x_0$}
           \end{cases}
\]
is $T(x) = x \log^{\Theta(1)} x$, which is different than the solution
of~$\Theta(x)$ for the recurrence without the $x/\log x$ term.

\end{remark}

\begin{thebibliography}{1}

\bibitem{ab}
M.~Akra and L.~Bazzi.
\newblock ``On the solution of linear recurrence equations.''
\newblock To appear, 1996.

\bibitem{clr}
Thomas~H. Cormen, Charles~E. Leierson, and Ronald~L. Rivest.
\newblock {\em Introduction to Algorithms}.
\newblock The MIT Press, Cambridge, Massachusetts, 1990.

\end{thebibliography}

\end{document}

