Divide and conquer is an important algorithm design based on recursion. The divide and conquer algorithm works by recursively breaking down into two or more sub problems of the same type. Until they become simple enough to solved directly.
What is the divide and conquer strategy?
The divide and conquer strategy solves a problem by:
- Divide: Breaking the problem into subproblems that are they become smaller instances of the same type of problem.
- Conquer: Conquer the subproblems by solving them recursively.
- Combine: Combine the solutions to the subproblems into the solutions for the original given problem.
More about Divide and Conquer –
For a clear understanding of the algorithm, let us consider a story. There was an old man who was a rich farmer and seven sons. He was afraid that when he died, his land and his possesions would be divided among his seven sons, and that they would quarrel with one another.
So he gathered them together and shows them seven stiks that he had tied together abd told them that anyone who could break the bundle would inherit everything. They all tried, but no one could break the bundle. Then the old man untied the bundle and broke thstick ine by one. The brothers decided that they should stay together and succed together. The moral for problem solvers is different. If we cant solve problem, divide it into parts, and solve one part at a time.
Advantages of Divide and Conquer –
Solving difficult problems: It is a powerful method for solving difficult problems. Dividing the problem into subproblems so that subproblems can be combined again is a major difficulty in designing a new algorithm. For many such problem this algorithm provides a simple solution.
Parallelism: Since it allows us to solve the subprblems independently, this allows for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance, because different subproblems can be executed on different processors.
Memory access: It naturally tend to make efficient use of memory caches. This is because once a subproblem is small, all its subproblems can be solved within the cache, without accessing the slower main memory.
Disadvantages of Divide and Conquer –
One disadvantage of this approach is that recursion is slow. This is beacause of the overhead of the repeated subproblem calls. Also the algorithm need stack for storing the calls. Actually this depends upon the implementation style. With large enough recursive base cases , the overhead of recursion can become negligible for many problems.
