Master theorem

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.

Given a relation of the form:

<math>T(n) = a T\left(\frac{n}{b}\right) + f(n) \;\;\;\; \emph{where} \;\; a \geq 1 , b > 1<math>

It is possible to determine an asymptotic tight bound according to these three cases:

Case 1:

<math>f(n) \in O\left( n^{\log_b a – \varepsilon} \right) \rightarrow T(n) \in \Theta\left( n^{\log_b a} \right) \;\;\;\; \emph{where} \;\; \varepsilon > 0<math>

Case 2:

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

Case 3:

<math>f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right), a f\left( \frac{n}{b} \right) \le c f(n) \rightarrow T(n) \in \Theta(f(n))\;\;\;\; \emph{where} \;\; \varepsilon > 0, c<1 <math>

note that the master theorem holds for <math>\left\lfloor \frac{n}{b} \right\rfloor\,<math> and <math>\left\lceil \frac{n}{b} \right\rceil\,<math> as well.

See also MacMahon's master theorem.

External link

• [1]