## Divide and Conquer method Illustrated

Divide and Conquer is one of the famous algorithmic techniques. It works with the philosophy that divide the whole problem into smaller managable chunks of subproblems and work out these small subproblems there by combining the intermediate partial solutions.

There are many famous examples which use the Divide and Conqure strategy, for example Binary search, Merge sort, Insertion sort, Quick sort etc.,

Let us take a small example of finding minimum and maximum elements in a given array. If we adapt a normal methodology it takes atleast 2*(n-1) comparisions. We can decrease the number of comparisions using this technique which results in [ Ceil(3*n/2)-2 ] comparisions.

The below is the code for finding MIN and MAX of the given array which was compiled and tested using GNU g++compiler.

//Author: Vasanth Raja Chittampally #include <iostream> using namespace std; void findMin(int [],int, int,int &, int &); int main() { int n,min,max; cout<<"Enter n:"; cin>>n; int a[n]; for(int i=0;i<n;i++) { cout<<"Enter a["<<i<<"]:"; cin>>a[i]; } findMin(a,0,n-1,min,max); cout<<"Minimun of the given array is: "<<min<<;endl; cout<<"Maximum of the gvien arrays is: "<<max<<endl; return 0; } void findMin(int a[], int left, int right, int &min, int &max) { if(left==right) { min=a[left]; max=a[right]; } else { int mid=(left+right)/2; findMin(a,left,mid,min,max); int left_min=min; int left_max=max; findMin(a,mid+1,right,min,max); int right_min=min; int right_max=max; if(left_min<right_min) min=left_min; else min=right_min; if(left_max>right_max) max=left_max; else max=right_max; } }

In this example it divides whole array into two equal parts recursively and tries to compare partial solutions to find the minimum and maximum elements.

T(n)=2T(n/2) + **2 ** —–>(2 comparisions are needed one for minimum and the other of maximum)

.

.

.

.

number of comparisions = [ Ceil(3*n/2)-2 ]

**The above number of comparisions can be verified by substituting in T(n)**

T(n)=2*[3*n/(2*2) – 2]+2

T(n)=3n/2-2 (hence verfied)