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:

1. 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)

2. f(n) = n^log_b^a

   If f(n) = Θ(n^log_b^a ) then T(n) ∈ Θ(n^log_b^a * lg n)

3. 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