In a divide and conquer approach, we solve a problem recursively, applying the following three steps at each level of recursion:

• Divide the problem into more than one subproblems that are smaller instances of the same problem.
• Conquer the subproblems by solving them recursively. Eventually, the subproblem sizes are small enough for them to be solved in a straightforward manner.
• Combine the solutions to the subproblems in the solution for the original problem.

When a subproblem is large enough to be solved recursively, we call that the recursive case. When a subproblem becomes small enough that recursion is no longer necessary, we say that we have reached to the base case. It is common to solve subproblems that are different from the original problem, in addition to the subproblems that are smaller instances of the main problem. Solving these problems is considered to be part of the combine step.

In Chapter 2, Sorting Algorithms and Fundamental Data Structures, we saw that the runtime complexity of merge sort was O(nlogn). We can also see that the worst-case running time T(n) of merge sort can be described by the following recurrence:

These kinds of recurrences arise frequently and characterize divide and conquer algorithms. If we generalize the recursion to the following:

Where a >= 1, b > 1 and f(n) is a given function, we have the recurrence for the worst-case running time of a divide and conquer algorithm that creates subproblems, each being of size 1/b of the original problem, and in which the combine steps together take f(n) time.

When it comes to divide and conquer algorithms, it is often easier to come up with this recursion, but harder to derive the runtime complexity. Fortunately, there are at least three methods to provide O bounds for these recurrences: the substitution method, the recursion tree method, and the master method. For the purpose of this book, we will only be focused on the master method.