Divide-and-Conquer
Divide-and-conquer is a problem-solving technique that breaks a complex problem into smaller, more manageable subproblems, solves each subproblem recursively until it bottoms out (i.e. reaches the recursive base case), and then combines their solutions to solve the original problem. It consists of three steps:
- Divide the problem into subproblems that are smaller instances of the same problem.
- Conquer the subproblems by solving them recursively.
- Combine the subproblem solutions to form a solution to the original problem.
Divide-and-conquer problems are analyzed using recurrences that describe the overall running time of an algorithm in terms of the running time of its subproblems. There are a few methods for solving recurrences. Namely, these are:
- The master method, which provides bounds for recurrences of the form , given constants , and a driving function .
- The substitution method,
- The recursion-tree method,
- The Akra-Bazzi method,
Examples
Square Matrix Multiplication (D&C and Strassen's Algorithm)
There are numerous ways to compute the product of two matrices. One way to do so is using a simple divide-and-conquer algorithm with two input matrices and , and one zero-initialized output matrix . In the algorithm:
- We will partition each matrix into four sub-matrices.
- We will recursively call the function for each of the eight pairs of submatrices.
- At the base case, each recursive call adds the product of the scalars and to the designated element of .
We can characterize the worst-case running time of this algorithm as . Since each recursive call multiplies two matrices, it contributes to the overall running time. Since there are eight recursive calls, can be expressed as
where is the base case, which is always constant since is updated in-place. The solution to the recurrence is .However, is a tad bit too long for large matrices. As such,