July 9, 2009

Member Rating

Curriki Rating**'NR'** - This resource has not been rated NR**'NR'** - This resource has not been rated

The resource has been added to your collection

Through this you will learn how to solve questions using the Divide and Conquer Method.

- Career & Technical Education > General
- Mathematics > General
- Science > General

- Grade 11
- Grade 12
- Higher Education
- Graduate
- Undergraduate-Upper Division
- Undergraduate-Lower Division

Curriki Rating**'NR'** - This resource has not been rated NR **'NR'** - This resource has not been rated

This resource has not yet been reviewed.

Not Rated Yet.

View Content **DIVIDE AND CONQUER METHOD**

**THEORY**

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:-**

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

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:

**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

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.

**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,

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.

Or

Our Terms of Service and Privacy Policies have changed. By logging in, you agree to our updated Terms and Policies.

Are you sure you want to logout?

Or