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 - e} ) for some constant e > 0 then T(n) Î Q (n^log_b^a)

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

   If f(n) = Q(n^log_b^a ) then T(n) Î Q(n^log_b^a * lg n)

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