Recent Articles

Master theorem

In the analysis of algorithms, the master 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{a}{b}<math>

is interpreted as either

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

or as

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

of the ratio

<math>\frac{a}{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 - \epsilon} \right)<math>

for some constant

<math>\epsilon > 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 + \epsilon} \right)<math>

for some constant

<math>\epsilon > 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