This is a paper that extends the Master Theorem 1 for more general use. To recap, the Master Theorem is about the complexity of a recurrence algorithm. It assumed the recurrence relation has the form

$T(n) = a T(n/b) + f(n)$

for $T(n)$ the complexity with input size $n$, which under divide-and-conquer will be broken down into $a$ pieces of subproblems of size $n/b$, and the cost of split-combine is $f(n)$. It requires $a$ and $b$ are constants and $T(1)=O(1)$. This notation assumes parameter to $T(n)$ are rounded to integer as well.

The solution of such recurrence depends on whether the cost of split $f(n)$ or the cost of subproblems $aT(n/b)$ are more expensive. If we define $c_{\phi}=\log_b a$, and

• If $f(n)=O(n^c)$ with $c<c_{\phi}$, then $T(n)=\Theta(n^{c_{\phi}})$. This is the case when the subproblem dominates the cost of split and the complexity is only due to solving the subproblems.
• If $f(n)=\Theta(n^{c_\phi}\log^k n)$ for $k\ge 0$, then $T(n)=\Theta(n^{c_\phi}\log^{k+1} n)$. This is when the subproblems and the cost of split are comparable.
• If $f(n)=\Theta(n^{c_\phi}\log^k n)$ for $k=-1$, then $T(n)=\Theta(n^{c_\phi}\log\log n)$
• If $f(n)=\Theta(n^{c_\phi}\log^k n)$ for $k<-1$, then $T(n)=\Theta(n^{c_\phi})$. Indeed, this means $f(n)=O(n^c)$ with $c<c_\phi$
• If $f(n)=\Omega(n^c)$ with $c>c_\phi$, the cost of split dominates the subproblems. Only in addition the regularity condition applies, i.e., $af(n/b) \le kf(n)$ for constant $k<1$ and when $n$ is fairly large, then $T(n)=\Theta(f(n))$. The regularity condition means the cost of split at the root problem dominates all cost of split at subproblems.

The Master Theorem cannot apply if $a$ or $b$ is not constant, or $a<1$, or the cost of split $f(n)$ is negative. This is where the Akra & Bazzi paper emerges:

The paper assumes a generalized recurrence relation of the form

$T(n) = g(n) + \sum_{i=1}^k a_i T(n/b_i + h_i(n))$

which $a_i>0, b_i>1$ are constants with $g(n)$ a positive non-decreasing function of the cost of split, and $\mid h_i(n)\mid =O(x/log^2 x)$ a small perturbation, for example to account for the rounding of $n/b_i$ to integers.

The paper starts with the above relation with $T(n)$ substituted with $u_n$ with $u_0$ a defined constant. Then it proves the continuous function $T(x)$ equals to $u_{\lfloor x\rfloor}$. Afterwards, the paper set up an order transform for any function $f(x)$ as

$F(s,p) = \int_1^s f(u) u^{-p-1} du$

and build up a relationship between $f(x)$ and $f(x/a)$ so that the latter can be expressed in terms of former. In this way, the theorem is established:

$T(n)=\Theta(n^p)+\Theta\left(n^p\int_1^n\frac{g(u)}{u^{p+1}}du\right))$

for $p$ the constant such that $\sum_{i=1}^k a_ib_i^{-p}=1$,

1. Jon L. Bentley, Dorothea Haken, and James B. Saxe. A general method for solving divide-and-conquer recurrences. SIGACT News, 12(3):6-44, 1980.

## Bibliographic data

@article{
title = "On the solution of linear recurrence equations",
author = "Mohamad Akra and Louay Bazzi",
journal = "Computational Optimization and Applications",
volume = "10",
number = "2",
pages = "195--210",
month = "May",
year = "1998",
}