Master theorem - Definition and Overview

In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. Suppose given such a relation of the form

<math>T(n) = a T\left(\frac{n}{b}\right) + f(n)\,<math>

where

<math>a \ge 1\,<math>

and

<math>b > 1\,<math>

are taken as constants and

<math>\frac{n}{b}\,<math>

is interpreted as either

<math>\left\lfloor \frac{n}{b} \right\rfloor\,<math> (the floor function)

or as

<math>\left\lceil \frac{n}{b} \right\rceil\,<math> (the ceiling function)

of the ratio

<math>\frac{n}{b}.<math>

Then we may bound the relation

<math>T(n)\,<math>

according to one of the following three cases:

Case 1: If

<math>f(n) \in O\left( n^{\log_b a - \varepsilon} \right)<math> (the big-O notation)

for some constant

<math>\varepsilon > 0\,<math>

then

<math>T(n) \in \Theta\left( n^{\log_b a} \right).\,<math>

Case 2: If

<math>f(n) \in \Theta\left( n^{\log_b a} \right)\,<math>

then

<math>T(n) \in \Theta\left( n^{\log_b a} \log(n)\right).\,<math>

Case 3: If

<math>f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)<math>

for some constant

<math>\varepsilon > 0<math>

and if

<math>a f\left( \frac{n}{b} \right) \le c f(n)<math>

for some constant

<math>c < 1<math>

and for some sufficiently large <math>n<math>, then <math>T(n) \in \Theta(f(n)).<math>

See also MacMahon's master theorem.