Divide and Conquer Algorithm

Divide and Conquer algorithm is a recursive problem-solving approach that solves the recursive problems by dividing them into subproblems, solve the subproblems recursively, and then combines the solutions of subproblems to solve the original problem.

There are three steps in the Divide and Conquer approach:

Divide: Dividing the sequence into two or more than two subsequences that are similar to the original sequence but smaller in size. For example, take a big organization, it will be difficult for a single person to handle all the work related to the organization. Therefore it is divided into different parts and managed by different people. Similarly, a sequence is divided into subsequence and solved separately.

Conquer: Solve the sub-problems recursively. here in the example, we have taken different parts are managed by individual people.

Combine: Combining these solutions to subsequence to create a solution to the original sequence. The example the basic idea of an organization is to get profit, so all the individuals working in different departments combine their work to get the final profit of the organization.

There are two fundamental of divide and conquer strategy:

1.Relational formula

2.Stopping condition

Relational Formula:

It is the formula that we should generate from the formula given. After generating the formulae then we should apply the divide and conquer approach, divide the problem and solve them individually.

Stopping Condition:

When we divide the problem to apply the divide and conquer approach, we need to know how much time do we need to apply the divide and conquer approach. The condition where we should stop applying divide and conquer is called the stopping condition.

The time complexity of the divide and conquer algorithm is calculated using the master's theorem

One important thing is that the main problem and subproblem should be of the same type, for example, the main problem is of sorting the subproblems should be also of sorting

Some of the examples where the Divide and Conquer algorithm is used are karatsubas algorithm for fast multiplication method, Strassen’s matrix multiplication, quick sort and merge sort algorithms, binary search, finding closest pair of points, the algorithm for fast Fourier transformation, maximum and minimum problems, etc

Example 1: Merge Sort

Merge sort is an efficient sorting algorithm and it uses Divide and Conquer approach.

To solve the merge sort problem firstly divide the given sequence into two equal subsequences, then solve the subsequences recursively using merge sort. after sorting, the subsequences merge all of them into a single sorted sequence to get the solution.

The following is an example:

In the above problem, the sequence in the first step is divided into two subsequences and it is done again and again until the sequence is of one element. Then the sequence is solved recursively. After solving it is then combined to become a single solution.

Example 2: Binary Search

Let’s take a sorted array A[] with n elements and find out whether K is present or not using Divide and Conquer approach. The normal solution for this problem is doing a linear search to find whether element K is present or not. this will take O(n) time complexity. but if we use the sorted property of the array we can apply the divide and conquer approach to solve efficiently in O(logn).

The idea of binary search is dividing the array into equal parts and comparing the middle term with K.If A[mid] is greater than K then K will not be present in the right part, so we will leave the right part and apply the same step in left part until we have found the element K.Similarly if A[mid] is less than K we have to search in the right part.

Solution Steps

Divide: Calculate the middle index of the array. if(A[mid] == k),then return 1. This is a case of a successful search.

Conquer: Recursively solve the smaller sub-problem

Generally, we will be solving problems using the divide and conquer approach by dividing the problem into only two subproblems

Subproblems are independent in the Divide and Conquer approach because every subproblem is working independently on different parts of the given input

This approach is the best algorithm design approach to learn about recursive problems solving methods

Pros:

Solve difficult algorithms with less time complexity than its counterpart. For example in binary search normally the time complexity is O(n), but if we solve the algorithm using the divide and conquer approach the time complexity is O(logn).

Since the subproblems are independent they can be solved differently.

Cons:

Since it is using recursion it consumes more space than the normal algorithm.

As we are dividing the problem recursion is done to small cases that will mean huge stacks of recursion are required.

As most of the algorithms are designed to use recursion, it is necessary that is requires high memory management.

How to identify divide and conquer problems:

When we have problems that look like the Divide and Conquer algorithm (such as merge sort) it will be useful

Most of the time, the algorithms we design are the most kind of like merge sort

If we have an algorithm that takes a list and does something with each element of the list, it might be able to use divide & conquer.

Conclusion:

Once you have got identified where to breakdown you’ll easily solve the algorithm problems. this is often one of all the best ways to decrease the time complexity of an algorithm