Master Theoram

               

2. Master Theoram:  

Master theorem is used in calculating the time complexity of recurrence relations 
(divide and conquer algorithms) .


It is solved in a simple and quick way.
General format :      T(n) = a T(n/b) + f(n)
where, n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed
  to have the same size. a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function.

f(n) = cost of the work done outside the recursive call
a ≥ 1 and b > 1 are constants, and
f(n) is an asymptotically positive function.

For solving recurrences we have :
Case 1. If f(n) < nlogba, then T(n) = Θ((nlogba).
Case  2.  If f(n) = nlogba, then T(n) = Θ((nlogba *log n).
 case 3. If f(n) > nlogba, then T(n) = Θ(f(n)).

Example :

Examples:2

 T(n)=5T(n/2)+Ө(n ^2)  

solutions

a=5

b=2                 on comparing n^2 to n^log25

f(n)=n^2         so time complexity=O(n^log25)

Do your self?

Q.1  T(n)=3T(n/2)+n

Q2. T(n)=4T(n/2)+n^2

Q3. T(n)=3T(n/2)+n^2

Q4. T(n)=16T(n/4)+n

Q5.  T(n)=4T(n/2)+logn

Q6.  T(n)=3T(n/4)+nlogn

Q7.  T(n)=4T(n/2)+n/logn

Q8. T(n)=16T(n/4)+n!

Q9. T(n)=3T(n/3)+√n

Q10. T(n)=√2T(n/√2)+logn

Answers:

Q1. Ө(n^log3)

Q2. Ө(n^2 logn)

Q3. Ө(n^2)

Q4. Ө(n^2)

Q5. Ө(n^2)

Q6. Ө(nlogn)

Q7. Ө(n^2)

Q8. Ө(n!)

Q9. Ө(n)

Q10. Ө(√n)