about Sociology - online encyclopedia

Categories: Asymptotic analysis

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. Suppose given such a relation of the form

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

where

$a \ge 1\,$

and

$b > 1\,$

are taken as constants and

$\frac{n}{b}\,$

is interpreted as either

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

or as

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

of the ratio

$\frac{n}{b}.$

Then we may bound the relation

$T(n)\,$

according to one of the following three cases:

Case 1: If

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

for some constant

$\varepsilon > 0\,$

then

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

Case 2: If

$f(n) \in \Theta\left( n^{\log_b a} \right)\,$

then

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

Case 3: If

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

for some constant

$\varepsilon > 0$

and if

$a f\left( \frac{n}{b} \right) \le c f(n)$

for some constant

c < 1

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

See also MacMahon's master theorem .

Categories: Asymptotic analysis

01-04-2007 01:30:44
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy

© 2005 About Sociology.com. All Rights Reserved. Terms of Use and Disclaimer