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

where

and

b > 1

are taken as constants and

is interpreted as either

or as

of the ratio

Then we may bound the relation

T (n)

according to one of the following three cases:

Case 1: If

for some constant

ε > 0

then

Case 2: If

then

Case 3: If

for some constant

ε > 0

and if

for some constant

c < 1

and for some sufficiently large $n$ , then