Massive Algorithms: Master theorem - Wikipedia, the free encyclopedia

Master theorem - Wikipedia, the free encyclopedia

The master theorem concerns recurrence relations of the form:

T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n) \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1

In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:

n is the size of the problem.
a is the number of subproblems in the recursion.
n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

Case 1

Generic form

If

f(n) = O\left( n^{c} \right)

where

c < \log_b a

(using Big O notation)

then:

T(n) = \Theta\left( n^{\log_b a} \right)

Example

T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2

As one can see from the formula above:

a = 8, \, b = 2, \, f(n) = 1000n^2

, so

f(n) = O\left(n^c\right)

, where

c = 2

Next, we see if we satisfy the case 1 condition:

\log_b a = \log_2 8 = 3>c

.

It follows from the first case of the master theorem that

T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)

Case 2

Generic form

If it is true, for some constant k ≥ 0, that:

f(n) = \Theta\left( n^{c} \log^{k} n \right)

where

c = \log_b a

then:

T(n) = \Theta\left( n^{c} \log^{k+1} n \right)

Example

T(n) = 2 T\left(\frac{n}{2}\right) + 10n

As we can see in the formula above the variables get the following values:

a = 2, \, b = 2, \, c = 1, \, f(n) = 10n

f(n) = \Theta\left(n^{c} \log^{k} n\right)

where

c = 1, k = 0

Next, we see if we satisfy the case 2 condition:

\log_b a = \log_2 2 = 1

, and therefore, yes,

c = \log_b a

So it follows from the second case of the master theorem:

T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)

Thus the given recurrence relation T(n) was in Θ(n log n).

Case 3

Generic form

If it is true that:

f(n) = \Omega\left( n^{c} \right)

where

c > \log_b a

and if it is also true that:

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

for some constant

k < 1

and sufficiently large

n

(often called the regularity condition)

then:

T\left(n \right) = \Theta\left(f(n) \right)

Example

T(n) = 2 T\left(\frac{n}{2}\right) + n^2

As we can see in the formula above the variables get the following values:

a = 2, \, b = 2, \, f(n) = n^2

f(n) = \Omega\left(n^c\right)

, where

c = 2

Next, we see if we satisfy the case 3 condition:

\log_b a = \log_2 2 = 1

, and therefore, yes,

c > \log_b a

The regularity condition also holds:

2 \left(\frac{n^2}{4}\right) \le k n^2

, choosing

k = 1/2

So it follows from the third case of the master theorem:

T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).

Thus the given recurrence relation T(n) was in Θ(n²), that complies with the f (n) of the original formula.

Read full article from Master theorem - Wikipedia, the free encyclopedia