Divide and Conquer

Sometimes a problem can be solved in many ways, but we chase for optimal solution. Optimal in terms of time complexity or space complexity according to the requirements. Divide and Conquer is one of the algorithms which reduces the time complexity of many problems. It is widely used in many computational problems.

Let us take a look at this algorithm.

Introduction:

Divide and conquer is an algorithm in computer science which recursively breaks down a problem into many subproblems, until they become simple enough to be solved. The solutions of the subproblems then combine to give a solution to the original problem. The idea is to decrease the difficulty of the problem.

Problems of sufficient simplicity are solved directly. Some authors consider that the name “divide and conquer” should be used only when each problem may generate two or more subproblems, and the name “Decrease and Conquer” has been suggested when discussing the single subproblem group. Subproblems are independent of each other. Divide and conquer is a top-down approach.

Divide and Conquer algorithm can be classified into following parts:

Divide: To divide the given problem into two or more subproblems.

Conquer: Conquer the subproblems by solving them using recursion.

Combine: Now Take the solutions to the sub-problems and merge them into one solution.

Algorithms based on Divide and Conquer:

· Quick sort

· Merge sort

· Strassen’s Matrix Multiplication

· Closest Pair of points

· Fast Fourier Transform (FFT)

· Karatsuba algorithm for fast multiplication

These are some standard algorithms based on divide and conquer method. Moreover, there are many other general problems that can be solved using divide and conquer method.

Advantages:

It is one of the best algorithms helps us solve difficult and often impossible looking problems in optimal method. It reduces the difficulty as it divides the problem into subproblems that are easily solvable.

It is used to solve the Tower of Hanoi problem which is a mathematical puzzle and problematic.

Providing the efficient algorithm is also an advantage of divide and conquer.

This approach is suitable for multiprocessing systems.

Divide-and-conquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory.

Disadvantages:

Divide and conquer algorithm is a recursive process, which is slow, which sometimes outweighs the advantages of Divide and conquer algorithm.

In some cases, when a problem is divided into subproblems, the same subproblem may occur more than two times. In cases like this it is better to identify and save some memory. This process is known as memoization.

Sometimes iterative method is preferable instead of recursive, for example when adding a large amount of numbers, in this case recursive do not benefit the solution, a simple loop is sufficient. Time complexity for iterative method is lesser here.

Recursion and Divide and Conquer:

The conquer method is responsible for recursion in divide and conquer algorithm. Divide and Conquer is a recursive process used to divide a problem into subproblems. This method usually allows us to reduce time complexity to a large extent. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

Partitioning:

Is the array always divided into two halves (n/2)?

We know that quick sort is an application of divide and conquer. In quick sort we pick a pivot element which helps in determination of partition in quick sort. Here the array is not always divided into two halves. This tells us that the partition can be done anyway in divide and conquer.

Complexity:

Bubble Sort, insertion sort, selection sort have time complexity of O(n²), whereas quicksort and mergesort (applications of Divide and Conquer) reduces the time complexity to O(nlog(n))

Linear Search has time complexity O(n), whereas Binary Search (an application Of Decrease and Conquer) reduces time complexity to O(log(n)).

Hence, we can conclude that solutions based on divide and conquer algorithm produce optimal outputs.

The time it takes for the divide and conquer algorithm to run is influenced by three things:

· The number of sub-parts into which a problem is split

· The ratio of the size of the beginning problem to the size of the sub-problem

· The number of steps required to divide and then combine the sub parts.

The algorithm divides the array by a constant amount and recursively sorts them, and finally merges the two sorted halves. The time complexity of this algorithm is O(nlog(n)), be it best case, average case or worst case.

Divide and conquer algorithms naturally tend to make efficient use of memory caches.

Dynamic Programming vs Divide and Conquer:

Divide and Conquer is similar to Dynamic Programming, both divides the problem into subproblems.

Dynamic programming uses a method called memoization, that means it does not evaluate subproblems many times. But divide and conquer does.

Subproblems are interdependent in dynamic programming but not in divide and conquer.

Is Binary search divide and conquer approach?

As per Wikipedia, some authors consider that the name “divide and conquer” should be used only when each problem may generate two or more subproblems. The name “decrease and conquer” has been proposed instead for the single-subproblem class. According to this definition, Merge Sort and Quick Sort comes under divide and conquer (because there are 2 sub-problems) and Binary Search comes under decrease and conquer (because there is one sub-problem).

Understanding divide and conquer implementation using an example merge sort.

Merge Sort:

It is an application of divide and conquer algorithm. This is one of the efficient sorting algorithms.

This algorithm divides the array into two halves, recursively sorts them, and finally merges them into a final sorted sequence.

Merge Sort Algorithm:

MergeSort(arr[], l, r)

If r > l

1. Find the middle point to divide the array into two halves:

middle m = l+ (r-l)/2

2. Call mergeSort for first half:

Call mergeSort(arr, l, m)

3. Call mergeSort for second half:

Call mergeSort(arr, m+1, r)

4. Merge the two halves sorted in step 2 and 3:

Call merge(arr, l, m, r)

Pseudocode:

· Declare left and right var which will mark the extreme indices of the array

· Left will be assigned to 0 and right will be assigned to n-1

· Find mid = (left+right)/2

· Call mergeSort on (left,mid) and (mid+1,rear) (The array is divided into two sub arrays, elements indexing from 0 to mid point and mid point+1 to last element)

· Above will continue till left<right

· Then we will call merge on the 2 subproblems based on comparison.

Time complexity: O(nlog(n)) (Best, average and worst cases)

Recurrence relation, T(n) = 2T(n/2) + θ(n)

The above example helps us understand the implementation of divide and conquer algorithm.