Divide and Conquer an Algorithm design technique

Hey, this is Shubham Mishra. In our previous post of Algorithm and its analysis, we have discussed all the algorithm, its designing and many another part. In the same post, In the algorithm designing section, I have mentioned a step that is 'Algorithm Strategy' for selecting a technique to design an algorithm. Out of all the, one very most popular among all is Divide and Conquer.

Now, let's start with divide and conquer technique for algorithm designing. In this technique, a problem is,

1. Broken down into smaller sub-problems.
2. The sub-problems are solved independently.
3. Merge all the solutions of all sub-problems to get the solution to the original problem.

Basically, If a problem seems too big but if the problem needs repetitive steps then it's better to divide the big problem and solve sub-problems. The sub-problems once solved then combine the solutions of sub-problems to get the result for the original problem. Now let's understand it with the algorithm below,

As the big problem is divided into small problems so similarly for time complexity calculation also the T(n) will also be calculated as the sum of Time complexities of the smaller subproblems. We will see few examples for divide and conquer but before that let's have a look on below pictures,

Divide and Conquer Algorithm Design

Now, let's go for some popular algorithms which are based on Divide and Conquer technique. We will start with the Finding Minimum and Maximum from a set of n elements.

In the normal approach, we take an array and iterate over it for n times to get the min or the max value.

 But in this approach, the time complexity is O(n), which is not good. So we will apply divide and Conquer technique. Basically, We will use Recursive algorithm  to find min and max. The recursive algorithm in its way uses the Divide and Conquer approach. In this algorithm, a big array is divided into two sub-array, if the array is too big else it returns the solution. When the subproblems return the solution lets suppose P1 and P2 have max1 and max2 as their solutions then while merging P1 and P2 their max1 is compared with the max2, whichever is greater is marked as the solution for P problem which was initially divided into P1 and P2.

In the above code, the get_min_and_max function is called on an array a, and it returns the minimum and maximum values.

Similar to the above there are many more algorithms are using Divide and Conquer approach. The list of applications are Binary search, Merge Sort, Quicksort, Multiplying long numbers, Constructing tennis tournament etc.

View my all posts for this blog, Shubham Mishra

Ok great, we are done with this post,  

Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.

Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)