Divide and Conquer is a very popular algorithm that many people use to solve problems. With Divide and Conquer, a problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the subproblems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those smallest sub-problem are solved. The solution of all sub-problems is finally merged in order to obtain the solution of the original problem.

Keep in mind that the divide and conquer algorithm is founded on recursion. It involves understanding a problem, separating it into subproblems, and combining the solutions to solve the larger problem just like recursion.

Divide and Conquer Strategy

1. Divide – breaking the problem into smaller sub-problems of the same problem
2. Conquer – solve the problem if it’s small enough(base case). If the problem is still not small enough, divide it and recursively solve its sub-problems. This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered ‘solved’ on their own.
3. Combine – combine solutions from sub problems to generate the solution for the original problem.

/**
 * Recursion used for factorial<br>
 * Start from the top and go to bottom, then calculation will start from bottom back to top
 */
private static int factorial(int num) {
    /**
     * validation
     */
    if (num < 0) {
        throw new IllegalArgumentException("num is invalid");
    }

    /**
     * base case, solve problem when it's small enough
     */
    if (num == 0) {
        return 1;
    }

    /**
     * recursive case, divide into sub-problems
     */

    return num * factorial(num - 1);
}

A problem can be also like this.

What are the disadvantages of Divide and Conquer?

Divide and Conquer algorithm requires recursion, which takes up more space than other processes. Your recursion stacks may overflow, causing the solution to fail.

Choosing base cases may also pose problems. Small, simple base cases typically lead to easier problems and solutions, while large base cases usually improve efficiency.

What are the advantages of Divide and Conquer?

Divide and Conquer algorithm helps solve complex problems relatively quickly and with much less effort(lines of code). It works well with processors because of their parallel structure. It also allows for easy storing and accessing by memory caches.

Where is Divide and Conquer being used?

Divide and Conquer is being used in these algorithms:

• Merge Sort
• Quick Sort
• Binary Search

This method usually allows us to reduce the time complexity by a large extent.

For example, Bubble Sort uses a complexity of O(n^2), whereas quicksort (an application Of Divide And Conquer) reduces the time complexity to O(nlog(n)). Linear Search has time complexity O(n), whereas Binary Search (an application Of Divide And Conquer) reduces time complexity to O(log(n)).

When do you use Divide and Conquer?

Divide and Conquer should be used when same subproblems are not evaluated many times. 

For example, Binary Search is a Divide and Conquer algorithm, we never evaluate the same subproblems again.

Here is an article that really caught my attention. It talks about how to use Divide and Conquer in business.

Source code on Github