# 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:

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

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

Case 1:

[itex]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[itex]

Case 2:

[itex]f(n) \in \Theta\left( n^{\log_b a} \right) \rightarrow T(n) \in \Theta\left( n^{\log_b a} \log(n)\right)[itex]

Case 3:

[itex]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 [itex]

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

• [1] (http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect04/node36.html#SECTION00063000000000000000)

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy