Home Theory Master Theorem for Divide and Conquer

Master Theorem for Divide and Conquer

by nikoo28
0 comment 2 minutes read

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 > bk, then T(n) = θ(nlogba)
  2.  If a=bk
    1.  if p > -1, then T(n) = θ(nlogba logp+1n)
    2.  if p = -1, then T(n) = θ(nlogba log(log n))
    3.  if p < -1, then T(n) = θ(nlogba)
  3.  If a < bk
    1.  if p >=0, then T(n) = θ(nk logpn)
    2.  if p <0, then T(n) = O(nk)

 

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More