Master Method

Document last modified:

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
- ε}) for some constant ε > 0 then T(n) ∈ Θ (n^log_b^a)
f(n) = n^log_b^a

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

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

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

then T(n) ∈ Θ(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) + Θ(n²)

Case 1: If f(n) = O(n^log_b^{a
- ε}) for some constant ε > 0 then T(n) ∈ Θ(n^log_b^a)

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

Yes. f(n) = Θ(n²) ∈ O(n^{lg 5
- ε}) = O(n^{2.32
- ε}) for ε ≈ 0.32

T(n) ∈ Θ(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) = Θ(n^log_b^a) then T(n) ∈ Θ(n^log_b^a lg n)

f(n) = n ∈ Θ(n^log₂²) = Θ(n¹)

T(n) ∈ Θ(n^log₂² lg n) = Θ(n lg n)

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

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

a = 5

b = 2

f(n) = Θ(n³)

log_b a = log₂ 5 ≈ 2.32

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

f(n) = Θ(n³) ∈ Ω(n^log₂^5+ε) = Ω(n^2.32+ε) for ε ≈ 0.68

OR

f(n) = Θ(n³) ∈ Ω(n^log₂^5+ε) = Ω(n^log₂⁵⁺³) (for ε=3) = Ω(n^log₂⁸) = Ω(n^log₂⁸) = Ω(n³)

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) ∈ Θ(n³)