Master Theorem for Divide and Conquer

All divide and conquer algorithms divides the problem into sub problems, each of which is part of the original problem, and then perform some additional work to compute the final answer. As an example, merge sort algorithm operates on two sub-problems, each of which is half the size of the original and performs O(n) additional work for merging. This gives the running time equation.

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

The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), first we try to find the recurrence relation for the problem. If the recurrence is of the below form then we can directly give the answer without fully solving it.

If the recurrence is of the form T(n) = aT(n/b) + θ(n ^k log ^p n), where a >= 1, b>1, k>=0 and p is a real number then,

1.  If  a > b^k, then T(n) = θ(n^log_ba)
2.  If a=b^k
   1.  if p > -1, then T(n) = θ(n^log_ba log^p+1n)
   2.  if p = -1, then T(n) = θ(n^log_ba log(log n))
   3.  if p < -1, then T(n) = θ(n^log_ba)
3.  If a < b^k
   1.  if p >=0, then T(n) = θ(n^k log^pn)
   2.  if p <0, then T(n) = O(n^k)