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] (http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect04/node36.html#SECTION00063000000000000000)
Template:Compu-lang-stubde:Master-Theorem it:Master theorem dell'analisi degli algoritmi he:שיטת האב