DIVIDE AND CONQUER

DIVIDE AND CONQUER

Divide and Conquer is one of the best-known general algorithm design technique. Divide-and-conquer algorithms work according to the following general plan:

1. A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.

2. The smaller instances are solved (typically recursively, though sometimes a different algorithm is employed when instances become small enough).

3. If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem.

The divide-and-conquer technique is diagrammed, which depicts the case of dividing a problem into two smaller sub problems, 

Examples of divide and conquer method are Binary search, Quick sort, Merge sort.

·         Definition:

     Given a function to compute on n inputs the divide-and-conquer strategy suggest splitting the inputs into k distinct subsets, 1 < K ≤ n, yielding k sub problems. These Sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole. If the Sub problems are still relatively large, then the divide-and-conquer strategy can possibly be reapplied. Often the sub problems resulting from a divide-and-conquer design are the same type as the original problem. For those cases the reapplication of the divide-and-conquer principle is naturally expressed by a recursive algorithm. Now smaller sub problems of the same kind are generated until eventually sub problems that are small enough to be solved without splitting are produced.