Master's Theorem

Master Method is a direct way to get the solution. The master method works only for following type of recurrences or for recurrences that can be transformed to following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are following three cases:

1. The running time is dominated by the cost of the leaves.

If f(n) = O$$(n^{log_ba-e})$$ then T(n) = $$\theta$$$$(n^{log_ba})$$for e>0

1. The running time is distributed throughout the tree.

If f(n) = Θ$$(n^{log_ba})$$ then T(n) = $$\theta$$$$(n^{log_ba}log(n))$$

1. The running time is dominated by the cost at the root.

If f(n) = $$\Omega$$$$(n^{log_ba+e})$$ then T(n) = $$\theta$$(f(n)) for e>0

only if f(n) satisfies the regularity condition:

af(n/b) <= cf(n) where c < 1. If this fails then Master Theorem cannot be applied.

______________________________________

Master theorem is not applicable for :

T(n) = kT(n/k) + nlogn

coz there is no polynomial difference between these two terms.

______________________________________