Divide and Conquer Algorithm | Introduction

Introduction of Divide and Conquer Algorithm

Many useful algorithms are recursive in structure, to solve a given problem, they call them to solve, recursive one or more time to deal with closely related subproblems.
these algorithms follow a divided and conquer approach.

They break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblem recursively and then combine these solutions
to create a solution to the original problem.

Divide:- The problem into a number of subproblems.
Conquer:- The subproblem by solving them recursively.
Combine:- it define as the solutions to the subproblem into the solution for the original problem

For Example

A={9,8,6,1,2,5,4,3}

Divide and Conquer Algorithm

Following, these are few standard algorithms that are Divide and Conquer algorithms.

1) Binary Search:- it is a searching algorithm.
In every step, the algorithm compares the input element x with the value of the middle element in the array.
As a result, If the values match, they return the index of the middle.
Otherwise, as a result, if x is less than the middle element.
then the algorithm recurs for the left side of the middle element, else recurs for the right side of the middle element.

2) Merge Sort:- it is also a sorting algorithm.
this algorithm divides the array into two halves, recursively sorts them and finally merges the two sorted halves.

3) Quicksort:- it is also a sorting algorithm. The algorithm picks a pivot element,

rearranges the array elements in such a way that all elements smaller than the picked pivot element move to the left side of the pivot, and all greater elements move to the right side.

therefore, the algorithm recursively sorts the subarrays on the left and right of pivot element.

4) Closest Pair of Points:- Find the closest pair of points in a set of points in the x-y plane.
These problems can be solved in O(n^2) time by calculating distances of every pair of points and compare the distances to find the minimum.
hence, The Divide and Conquer (D &C) algorithm solve the problem in O(nLogn) time.

5) Strassen’s Algorithm:- This algo is an efficient algorithm to multiply two matrices.
therefore, in this algorithm A simple method to multiply two matrices need 3 nested loops and is O(n^3).
as a result Strassen’s algorithm multiplies two matrices in O(n^2.8974) time.