DIVIDE AND CONQUER METHOD
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
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,
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!
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.
1. Ellis Horowitz and Sartaj Sahni, Fundamentals of Computer Algorithms
, Computer Science Press, Maryland, 1978, 626 pages