Master Theorem

T(n) = aT(n/b) + f(n), a ≥ 1; b > 1.

T(n) can be bounded asymptotically as follows:

If f(n) = O(n^log_ba/n^ε) for som constant ε > 0, then T(n) = Θ(n^log_ba).

If f(n) = Θ(n^log_ba), then T(n) = Θ(n^log_balogn).

If f(n) = Ω(n^log_ban^ε) for som constant ε > 0, and if af(n/b) ≤ cf(n) for some constant c < 1 and for all sufficiently large n, then T(n) = Θ(f(n)).

General Idea

f(n) is compared with n^log_ba:

if f(n) is (polynomially) smaller then n^log_ba, then T(n) = Θ(n^log_ba).

if f(n) is (polynomially) greater then n^log_ba, then T(n) = Θ(f(n)).

if f(n) is Θ(n^log_ba), then T(n) = Θ(f(n)logn).

Examples

T(n) = 9T(n/3) + n:

a = 9.

b = 3.

f(n) = n.

n^log_ba = n^log₃9 = n².

Since f(n) = O(n^log₃9-ε) = O(n) for ε=1, case 1 implies that T(n)=Θ(n²).

T(n) = T(2n/3) + 1:

a = 1.

b = 3/2.

f(n) = 1.

n^log_ba = n^log_3/21 = n⁰ = 1.

Since f(n) = Θ(1), case 2 implies that T(n)=Θ(logn).

3T(n/4) + nlogn:

a = 3.

b = 4.

f(n) = nlogn.

n^log_ba = O(n^0.793).

Since f(n) = Ω(n^log₄3+ε), where ε ≅ 0.2, and af(n/b) ≤ cf(n) for c=a/b, case 3 implies that T(n)=Θ(nlogn).