DIVIDE AND CONQUER METHOD

THEORY





 


The term "Divide and Conquer" simply means dividing the big/large concentrations into small ones and then rule them. This was the technique that was used by some old rulers and kings to rule their own provinces and even to conquer the new ones. They used to divide the provinces on different behalf's like religion, work, caste or creed. We are going to do the same in our problems, but the division will be on the basis of the size of problem, the nature of the problem and the type of the problem.

We will be dividing the problem into further smaller groups until individual elements are present and then recombining all of them to form a combined solution for a one step higher level problem. Then, we will be combining all of these solutions to go one step further ahead and go on till the solution has arrived. So due to the nature of this technique it is called as a top-down technique.

Often the sub-problems that are created by dividing the problem are of the same type as that of the original problem, so for these problems the reapplication of the divide and conquer algorithm is expressed in a recursive way (calling itself again and again). And with that the smaller and smaller sub-problems of the same kinds are generated until sub-problems that are small enough to be solved by themselves without splitting are created.


The three steps that we have to do in order to solve these problems are:-








 

1. Dividing the main problem recursively into smaller ones.

2. Solving these smaller sub-problems according to the main question.

3. And then recombining them to reach the top level.

So these are basically the 3 steps that we have to perform in every problem. So let me show this pictorially to make it even more clear,


In this figure A is the main problem which is further subdivided as shown.





 

This figure shows the way in which the problems are sub-divided from top to bottom.

So through this tree formation, the real problem is now shifted to the leaves of this tree. Now whatever operation that we want to perform is performed trivially on the leaves until we find the solution.

Now let's understand this topic in a simpler way. Suppose we have to search for a number in a given set of sorted numbers, like we have to search 9 out of (3,5,7,9,12,13,21,24,27). Searching means finding whether the number is present in the given list or not.
So the one way to do this is to go one by one and look for every element and compare it with the given number. This is not possible if the given is very big.
The next way is to divide the list every time into two sub-lists. Then, check into which list the number may exist as the list is sorted, and always compare the middle element (N/2+1/2) or N/2 depending upon the odd and even nature of the total numbers present in the list respectfully, with the given number to be searched, as shown.






 


 

Figure showing a search algorithm in a given list, it is also called as binary search


 


 

In this, the number 9 is compared to 12 first as the number is smaller than this so the first sub- list, is selected i.e (3,5,7,9). Again the number is compared to 5 as 9>5 so second list is selected, and then we the list as (7,9) the number is compared to 7 first and then second sub-list is selected which is(9). And finally we found the number.


This type of search method takes approximately O(log n)time complexity, rather than the O(n) complexity in Normal search.


The general expression for finding the complexity of the divide and conquer algorithms is given by recurrence of the form:









 

T(n) = T(1) if (n=1)

= a *T(n/b) +f(n) if(n>1)


Here a,b,f(n)and n are the function constants that will be different for different problems.So now we are done with the theory. Now we are going to read a few problems solved with the divide-and-conquer algorithm along with their pseudo codes. Get ready!


EXAMPLES

So now let's go through some examples of this method in next section.
BIBLIOGRAPHIC CITATIONS
ARTICLE
1. This click here Divide And Conquer Algorithm Technique By: Barzan "Tony" Antal.

BOOKS
1. Ellis Horowitz and Sartaj Sahni,
Fundamentals of Computer Algorithms, Computer Science Press, Maryland, 1978, 626 pages








Do NOT follow this link or you will be banned from the site!

Non-profit Tax ID # 203478467