Divide and Conquer Algorithms

A divide and conquer algorithm is a strategy of solving a large problem by

1. breaking the problem into smaller sub-problems
2. solving the sub-problems, and
3. combining them to get the desired output.

How Divide and Conquer Algorithms Work?

Here are the steps involved:

1. Divide : Divide the given problem into sub-problems using recursion.
2. Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
3. Combine: Combine the solutions of the sub-problems which is part of the recursive process to get the solution to the actual problem.

Let us understand this concept with the help of an example.

Here, we are going to sort an array using the divide and conquer approach (ie. merge sort).

1. Let the given array be:

   

   Array for merge sort

2. Divide the array into two halves.

   

   Divide the array into two subparts

   
   Again, divide each subpart recursively into two halves until you get individual elements.

   

   Divide the array into smaller subparts

3. Now, combine the individual elements in a sorted manner. Here, conquer and combine steps go side by side.

   

   Combine the subparts

Advantage of Divide and Conquer Algorithm

• The complexity for the multiplication of two matrices using the naive method is O(n3), whereas using the divide and conquer approach (ie. Strassen's matrix multiplication) is O(n2.8074). Other problems such as the Tower of Hanoi are also simplified by this approach.
• This approach is suitable for multiprocessing systems.
• It makes efficient use of memory caches.

---

Divide and Conquer Application

• Binary Search
• Merge Sort
• Quick Sort
• Strassen's Matrix multiplication
• Karatsuba Algorithm