Master Method for Solving Recurrences

What makes the master method so awesome is that it can be thought of as a "black box" for solving recurrences. This means that you give it some inputs and it tell tell you the running time of the algorithm. However, it only works when all subproblems have the same size. For example in each recursive call to MergeSort, each recursive call does work on size n/2.

Base Case:

T(n) ≤ a constant c, for all sufficiently small n

For larger n:

T(n) ≤ aT(n/b) + O(n^d) 

1. a is the number of recursive calls
2. b is the factor by which the problem size shrinks. It must be greater than one or the problem will never get any smaller
3. d is the exponent of the combining time. It can be as small as 0, which indicates it takes linear time.

a, b, d must all be constants and independent of the input size.
So the master method is:

In the first case, the base for the logarithm doesn't matter because a base will only change the amount by a constant factor. However, in the third case, the base matters a lot because it could make the difference between linear and quadratic time.

Let's look at MergeSort as an example. We know T(n) = 2T(n/2) + O(n). We have a=2, b=2, and d=1. a=b^d so we are in case 1. The running time will be O(n^dlogn) which is just O(nlogn).

For binary search, we split the problem into two with n/2 input size each BUT we only work in one of them and just compare the element you're searching for with the center element, which takes constant time. Thus, we have a=1, b=2, d=0 and a=b^d so the overall runtime will be O(logn).