Divide And Conquer Algorithms

The D & C algorithm works by recursively breaking down a problem into two or more sub problems of the same type, until they become simple enough to be solved directly. The solutions to the sub problems are then combined to give a solution to the original problem.


The D & C strategy solves a problem by:

• Divide: Breaking the problem into sub problems that are themselves smaller instances of the same type of problem. 
• Recursion: Recursively solving these sub problems. 
• Conquer: Appropriately combining their answers.

Does D&C always work?

As per the definition of D & C, the recursion solves the subproblems which are of the same type. For all problems it is not possible to find the subproblems which are the same size and D & C is not a choice for all problems.

As an example, consider the Tower of Hanoi problem. This requires breaking the problem into subproblems, solving the trivial cases and combining the subproblems to solve the original problem. Dividing the problem into subproblems so that subproblems can be combined again is a major difficulty in designing a new algorithm. For many such problems D & C provides a simple solution.

Advantages of D&C:

• Solving Difficult Problems
• Parallelism : Since sub problems can be solved independently, multiprocessor machines like shared memory system need not be planned in advance.
• Memory Access : D & C algorithms 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 D&C:

• Recursion is slow i.e. Since it needs stack for storing the calls but the overhead of recursion is negligible with large enough recursive base cases.
• It can be more complicated than iterative approach if the problem is simple.

Divide and Conquer Applications:

• Binary Search 
• Merge Sort and Quick Sort 
• Median Finding 
• Min and Max Finding 
• Matrix Multiplication 
• Closest Pair problem