What is divide and conquer algorithm?

Answer:

Divide and Conquer technique is helpful to solve the problems and can be divided into the following three parts:

Divide:- This involves dividing the problem into smaller sub-problems.

Conquer:- Solve sub-problems by calling recursively until solved.

Combine:- Combine the sub-problems to get the final solution of the whole problem.

The difficult problem can be solved easily. It divides the entire problem into subproblems thus it can be solved parallelly ensuring multiprocessing.

Efficiently uses cache memory without occupying much space.

Reduces time complexity of the problem.

It involves recursion which is sometimes slow.

Efficiency depends on the implementation of logic.

It may crash the system if the recursion is performed rigorously.

1. Quicksort (Sorting algorithm)

2. Merge Sort (Also a sorting algorithm)

3. Closest Pair of Points (The problem is to find the closest pair of points in a set of points in the x-y plane)

4. Strassen’s Algorithm (An efficient algorithm to multiply two matrices)

5. Cooley–Tukey Fast Fourier Transform (FFT) algorithm (The most common algorithm for FFT)

6. Karatsuba algorithm for fast multiplication.