Master Theorem

The Master Theorem is used for solving recurrence relations. The syntax for the recurrence relation as follows 

The syntax of the recurrence relation

Here, 

n = size of  the problem

a = number of subproblems in the recursion and a>=1 

n/b = size of each sub problem 

 

b>1, k>=0, and p is a real number

The complexity of the recurrence relation can be calculated directly by using the following  three golden rules:

pics from google