Massive Algorithms: Master theorem - Wikipedia, the free encyclopedia

Master theorem - Wikipedia, the free encyclopedia
In the analysis of algorithms, the master theorem provides a solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.

Algorithms such as above can be represented as a recurrence relation

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

. This recursive relation can be successively substituted into itself and expanded to obtain expression for total amount of work done.

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:

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

where

c < \log_b a

then:

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

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

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

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)

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

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)

Case 3:

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)

T(n) = 2 T\left(\frac{n}{2}\right) + n^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).

Application to common algorithms

Algorithm	Recurrence Relationship	Run time	Comment
Binary search	$T(n) = T\left(\frac{n}{2}\right) + O(1)$	$O(\log n)$	Apply Master theorem case $c = \log_b a$ , where $a = 1, b = 2, c = 0, k = 0$ ^[3]
Binary tree traversal	$T(n) = 2 T\left(\frac{n}{2}\right) + O(1)$	$O(n)$	Apply Master theorem case $c < \log_b a$ where $a = 2, b = 2, c = 0$ ^[3]
Optimal Sorted Matrix Search	$T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)$	$O(n)$	Apply Akra-Bazzi theorem for $p=1$ and $g(u)=\log(u)$ to get $\Theta(2n - \log n)$
Merge Sort	$T(n) = 2 T\left(\frac{n}{2}\right) + O(n)$	$O(n \log n)$	Apply Master theorem case $c = \log_b a$ , where $a = 2, b = 2, c = 1, k = 0$