A Brief Introduction to Divide and Conquer Algorithms

Divide and conquer is a class of algorithm that involves dividing a problem into many equivalent subproblems, solving them, then combining the results to get an answer to the original problem. These types of algorithms typically apply recursion, following three steps:

1. Divide: Divide the problem into several subproblems, that are smaller instances of the same problem.

2. Conquer: Solve the subproblems recursively.

3. Combine: Combine the solutions to the subproblems to end up with a solution to the original problem.

When we reach a simple enough instance of subproblem, we can solve it using simple steps that don’t include further recursive calls. We refer to this as the base case of the problem. The idea of divide and conquer is that each subproblem will eventually reduce to the base case, and the base solution can be used to in turn solve all the recursive calls that came before.

When we encounter divide and conquer algorithms, we want to be able to analyze their run time, as with any sort of algorithm. There are three main ways that we can analyze divide and conquer algorithms. The first method is the substitution method, in which we guess the bound and use mathematical induction to prove our guess. This can be an effective strategy when the algorithm is simple, however it can prove challenging in most cases.

The second method is the recursion tree method, which involves converting the…