0

8.5kviews

Explain the general procedure of divide and conquer method.

**1 Answer**

0

8.5kviews

Explain the general procedure of divide and conquer method.

3

879views

written 2.1 years ago by |

- 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
as follows:*three parts***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

ADD COMMENT
EDIT

Please log in to add an answer.