Explain the general procedure of divide and conquer method.

880views

written 2.2 years ago by

binitamayekar ★ 6.4k

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:

Divide-and-Conquer

The problem with more recursive steps looks as follows:

Divde-and-Conquer BIG

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:

ADD COMMENT EDIT