Divide and conquer formula described

Divide and Conquer is definitely an algorithmic paradigm (sometimes mistakenly known as “Divide and Concur” – an interesting and apt name), much like Greedy and Dynamic Programming. An average Divide and Conquer formula solves an issue while using following three steps.

1. Divide: This requires dividing the issue into some sub problem.

2. Conquer: Sub problem by calling recursively until sub problem solved.

3. Combine: The Sub problem Solved so that we’ll get find problem solution.

Listed here are some standard algorithms that follows Divide and Conquer formula.

Quicksort is really a sorting formula. The formula picks a pivot element, rearranges the array elements in a way that elements smaller sized compared to selected pivot element proceed to left side of pivot, and all sorts of greater elements proceed to right side. Finally, the formula recursively sorts the subarrays on right and left of pivot element.

Merge Sort is another sorting formula. The formula divides the array in 2 halves, recursively sorts them and lastly merges the 2 sorted halves.

Nearest Set of Points The issue is to obtain the nearest set of points in some points in x-y plane. The issue could be solved in O(n^2) time by calculating distances of each and every set of points and evaluating the distances to obtain the minimum. The Divide and Conquer formula solves the issue in O(nLogn) time.

Strassen’s Formula is an excellent formula to multiply two matrices. An easy approach to multiply two matrices need 3 nested loops and it is O(n^3). Strassen’s formula multiplies two matrices in O(n^2.8974) time.

Cooley-Tukey Fast Fourier Transform (FFT) formula is easily the most common formula for FFT. It’s a divide and conquer formula which fits in O(nlogn) time.

Karatsuba formula for fast multiplication it will multiplication of two n-digit figures in for the most part single-digit multiplications generally (and just when n is really a power 2). Therefore, it is quicker than the classical formula, which requires n2 single-digit products. If n = 210 = 1024, particularly, the precise counts are 310 = 59, 049 and (210)2 = 1, 048, 576, correspondingly.

Divide And Conquer formula :

DAC(a, i, j)

Recurrence Relation for DAC formula :

This really is recurrence relation for above program.

           O(1) if n is small

T(n) =     f1(n)   2T(n/2)   f2(n)

Example:

To obtain the maximum and minimum aspect in confirmed array.

Input:

Output: The minimum number inside a given array is : 12

The utmost number inside a given array is : 250