Divide and Conquer

Divide and conquer method

Divide and conquer is an algorithmic paradigm in which the problem is repeatedly divided into subproblems until we reach a point where each problem is similar and atomic, i.e., can’t be further divided.

At this point, we can start solving these atomic problems and combining (merging) the solutions together.

This approach allows us to break down a difficult problem into subproblems that can be easily solved, reducing the overall degree of difficulty. However, this approach uses recursion, which is slow. Therefore, in the cases with a large $n$, this disadvantage might outweigh the advantages of this approach.

Let’s look at how the divide and conquer technique can be used to solve the problem of converting uppercase alphabets to lowercase.

The divide and conquer solution has the following three steps:

Divide:

Break the problem at hand into smaller subproblems. This step can be achieved recursively by dividing the problem until no further division is possible.