Divide and Conquer

Here’s a problem-solving paradigm with a long history.

About

The divide and conquer strategy involves breaking down a problem into multiple independent subproblems, solving the subproblems (recursively), and combining those solutions into a solution for the original problem.

If the original problem is broken down into a single subproblem, it is called a decrease and conquer strategy, and is very efficient to solve (via tail recursion or a simple loop).

Tools

To analyze the complexity of these things, you'll generally need to solve recurrence relations.

Decrease and Conquer Examples

Implementation of these is left as an exercise for you:

Divide and Conquer Examples

Mergesort

Quicksort

Finding the Median

Matrix Multiplication

FFT