Master Method

T(n) = a * T(n/b) + f(n) where n/b replaces either ën/bû or én/bù
a ³ 1 the number of subproblems
b > 1
f(n) = D(n)+C(n) is a function describing the cost of dividing and combining

T(n) can be asymptotically bounded for 3 cases as follows:

f(n) < n^log_b^a Intuitively: cost is dominated by leaves.

If f(n) = O(n^log_b^{a
- e}) for some constant e > 0 then T(n) Î Q (n^log_b^a)
f(n) = n^log_b^a

If f(n) = Q(n^log_b^a) then T(n) Î Q(n^log_b^a * lg n)
f(n) > n^log_b^a Intuitively: cost is dominated by root.

If f(n) = W(n^log_b^{a
+e}) for some constant e > 0 and

af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n

then T(n) Î Q(f(n))

i.e. f(n) is polynomially greater than n^log_b^a

Use the Master Method to asymptotically bound T(n)

T(n) = 5T(n/2) + Q(n²)

Case 1: If f(n) = O(n^log_b^{a
- e}) for some constant e > 0 then T(n) Î Q(n^log_b^a)

Determine: a, b, f(n) and log_ba
- a = 5
- b = 2
- f(n) = Q(n²)
- log_b a = log₂ 5 ≈ 2.32
Is f(n) Î O(n^{lg 5
- e}) for e > 0 ?

Yes. f(n) = Q(n²) Î O(n^{lg 5
- e}) = O(n^{2.32
- e}) for e ≈ 0.32

T(n) Î Q(n^log₂⁵)

2. T(n) = 2T(n/2) + n

Determine: a, b, f(n) and log_b(a)

a = 2

b = 2

f(n) = n

log_b a = log₂ 2 = lg 2 = 1

Case 2: If f(n) = Q(n^log_b^a) then T(n) Î Q(n^log_b^a lg n)

f(n) = n Î Q(n^log₂²) = Q(n¹)

T(n) Î Q(n^log₂² lg n) = Q(n lg n)

3. T(n) = 5T(n/2) + Q(n³)

Determine: a, b, f(n) and log_b(a)

a = 5

b = 2

f(n) = Q(n³)

log_b a = log₂ 5 ≈ 2.32

Case 3: If f(n) = W(n^log_b^a+e) for some constant e > 0

f(n) = Q(n³) Î W(n^log₂^5+e) = W(n^2.32+e) for e ≈ 0.68

and af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n

5(n/2)³ ≤ cn³

5n³/8 ≤ cn³

c = 5/8 < 1

then T(n) Î Q(n³)