Master theorem

The master theorem concerns recurrence relations of the form:

• n is the size of the problem.

• a is the number of subproblems in the recursion.

• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

• f (n) is the cost of the work done outside the recursive calls.

Case 1

If   

Where  

Then 

Case 2

If   k ≥ 0 and 

Where 

Then 

Case 3

If     where 

and    for some constant and sufficiently large n

Then