Books Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Latest:- Important tips to get an Off Campus Placements
0 like 0 dislike
in Examples, Exercises and Projects by (562 points)
edited by

In this article,you will know

  1. Divide and conquer strategy
  2. Its problems with solutions

1 Answer

0 like 0 dislike
by (562 points)
selected by
Best answer

Divide and Conquer  Strategy

  • A control abstraction indicates the way in which an actual program perform its task based on divide and conquer strategy.
  • It clearly shows the flow of control,but the primary operations are specified by other procedures.
  • The control abstraction is written either recursively or iteratively.
  • However ,the basic  functionality of either method is same.
  • Consider the algorithm,divide and conquer given below.
  • The algorithm is initially involved as DNC(P) ,where P is the problem to be solved.
  • P is a boolean valued function used for determining whether the input size is small enough to compute the answer without any splitting.If this is so,the function S is involved ,otherwise the problem P is broken down into smaller sub problems such as P1,P2,.......Pk.
  • These sub problems are solved by recursive applications of divide and conquer .Combine is a function that can find the solution to P by using the solutions to the K subproblems.
  • If the size of P is n and the size of the K sub problems are n1,n2,....nk  respectively.
  • Then ,the computing time of divide and conquer is described by the recurrence relation.


Control Abstraction for Divide and Conquer

Algorithm DNC(P)

  1. {

  2. if P then return S(P)

  3. else

  4. {

  5. divide P into smaller instances P1,Px,....Pk.

  6. Apply DNC to each of these sub problems. return combine(DNC(P


  7. }

P)Show the recurrence T(n)=4T(n/2)+n ,where n≥1 and is a power of 2.


Let ,n=2k and T(2k)=tk 


⇒tk=4tk-1+2k            .........     (i)

Replacing k by k-1 we get,

⇒tk-1=4tk-2+2k-1       ................(ii)

Multiply eq(ii) by 2 ,we get

⇒2tk-1=8tk-2+2k        ................(iii)

Substract (iii) from (i) ,we get









Putting back n, we get



P:2)Solve the following recurrence relation   T(n)=4T(n/2)+n2 ,where n>1 and is equal to power of 2.


Recurrence relation,T(n)=4T(n/2)+n2

Since n>1 and is power of 2 ,

put n=2k and T(2k)=tk to get,

⇒tk=4tk-1+22k          .......   (i)

And replacing k by k-1 ,we get

⇒tk-1=4tk-2+22(k-1)     ........(ii)

mulitiply 4*(ii) and subtract equation (i) from it,we get



 ⇒  tk-8tk-1+16tk-2=0

Putting tk=xk,we get


⇒   x2-8x+16=0


Therefore,T(n)£O(n2 logn)


3.3k questions

7.1k answers


4.6k users


About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © Social::   |  |