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",
}