General Procedure of Divide-and-Conquer Method

• In simple words, Divide-and-Conquer break down the main problem into small sub-problems. Then solve that sub-problem independently, and at last combine the solutions of small sub-problems as a solution for the main problem.
• Divide-and-Conquer creates at least two sub-problems, a divide-and-conquer algorithm makes multiple recursive calls.
• Some divide-and-conquer algorithms create more than two sub-problems also.
• Divide-and-Conquer solve sub-problems recursively, each sub-problem must be smaller than the original problem, and there must be a base case for sub-problems.
• Divide-and-Conquer algorithms have three parts as follows:
  • Divide the problem into a number of sub-problems that are small instances of the main problem.
  • Conquer the sub-problems by solving them recursively. If they are small enough, solve the sub-problems as base cases.
  • Combine the solutions of the sub-problems as one complete solution for the main problem.

Diagrammatic Representation of General procedure of Divide-and-Conquer Method:

The problem with more recursive steps looks as follows:

Benefits of Divide-and-Conquer:

• Easily solve large problems faster than other algorithms.
• It solves simple sub-problems within the cache memory instead of accessing the slower main memory.
• It supports parallelism because sub-problems are solved independently.
• Hence, the algorithm made using this approach runs on the multiprocessor system.

Drawback of Divide and Conquer:

• It uses recursion therefore sometimes memory management is a very difficult task.
• An explicit stack may overuse the space.
• It may crash the system if the recursion is carried out rigorously greater than the stack present in the CPU.

Applications of Divide and Conquer:

There are lots of applications of this divide-and-conquer approach as follows:

• Merge Sort
• Quick Sort
• Binary Search
• Tower of Hanoi
• Closest Pair of Points
• Karatsuba Algorithm
• Strassen's Matrix multiplication
• Cooley-Tukey Fast Fourier Transform (FFT) algorithm
• Finding the maximum and minimum of a sequence of numbers