Divide and Conquer Algorithm

Divide and Conquer is an algorithm design paradigm that is used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more subproblems, solve them in turn, and compose their solutions to solve the given problem. Problems of sufficient simplicity can be solved directly.

A typical Divide and Conquer algorithm solves a problem using the following three steps.

1. Divide: Break down the given problem into subproblems of same type.
2. Conquer: Solve these subproblems recursively and independently.
3. Combine: Merge the answers of the subproblems to get the solution to the problem.

Strategy to solve a problem using Divide and Conquer approach

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.

Fundamentals of Divide & Conquer Strategy

There are two fundamental of Divide & Conquer Strategy —

1. Relational Formula is where we apply D&C Strategy, i.e. we break the problem recursively & solve the broken sub-problems.

2. Stopping Condition is the condition where recursion steps of D&C is needed to stop.

Divide and Conquer vs Dynamic approach

In the divide and conquer approach, the result of each subproblem is not stored for future reference, whereas in a dynamic approach, the result of each subproblem is stored for future reference.

Use the divide and conquer approach when the same subproblem is not solved multiple times. Use the dynamic approach when the result of a subproblem is to be used multiple times in the future.

Applications of Divide and Conquer Algorithm:

Following are some of the algorithms that works on the principle of Divide and Conquer.

1. Binary Search is a searching algorithm that finds the position of a target value within a sorted array.
2. Quick Sort is a sorting algorithm that selects a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays; the sub-arrays are then sorted recursively.
3. Merge Sort is a sorting algorithm that divides the array in two halves, recursively sorts them and finally merges the two sorted halves.
4. Closest Pair of Points is a problem which can be solved in O(n²) time by calculating distances of every pair of points and comparing the distances to find the minimum.
5. Cooley–Tukey Fast Fourier Transform (FFT) Algorithm is a divide and conquer algorithm which works in O(nlogn) time.
6. Strassen’s Algorithm is an efficient algorithm to multiply matrices.
7. Karatsuba Algorithm is a fast multiplication algorithm that reduces the multiplication of two n-digit numbers to at most single-digit multiplications.

• Finding the maximum and minimum of a sequence of numbers.
• Tower of Hanoi.

Advantages:

1. Solving difficult problems

Divide and conquer is a powerful tool for solving conceptually difficult problems: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem.

2. Algorithm efficiency

The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. For instance, it was the key to the quicksort and mergesort algorithms, fast Fourier transforms, the Strassen algorithm for matrix multiplication and Karatsuba’s fast multiplication method. In all these examples, the D&C approach led to an improvement in the asymptotic cost of the solution.

3. Parallelism

Divide-and-conquer algorithms are adapted for execution in multi-processor machines because distinct sub-problems can be executed on different processors. It does not involve any modification and is handled by systems incorporating parallel processing.

4. Memory access

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

5. Roundoff control

Divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method. It is also more proficient than that of its counterpart Brute Force technique.

Disadvantages:

• Since most of its algorithms are designed by incorporating recursion, it necessitates high memory management.
• An explicit stack may overuse the space.
• The recursion is slow, which in some cases outweighs any advantages of the divide and conquer process.
• It may even crash the system if the recursion is performed rigorously greater than the stack present in the CPU.
• It can sometimes become more complicated than a basic iterative approach, especially in cases with a large n.