• The Master Method is used for solving the following types of recurrence
  

• with a≥1 and b>1 be constant & f(n) be a function

• In the function to the analysis of a recursive algorithm, the constants and function take on the following significance:

• 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 sum of the work done outside the recursive calls, which includes the sum of dividing the problem and the sum of combining the solutions to the subproblems.

• It is not possible always bound the function according to the requirement, so we make three cases which will tell us what kind of bound we can apply on the function.

I have prepared handwritten notes...kindly read them and you'll be able to solve all the problems trust me :

Note : Just ignore any constants you encounter since they dont affect time complexity

Solved Examples