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
if P then return S(P)
divide P into smaller instances P1,Px,....Pk.
Apply DNC to each of these sub problems. return combine(DNC(P
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,
Multiply eq(ii) by 2 ,we get
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.
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
mulitiply 4*(ii) and subtract equation (i) from it,we get
Putting tk=xk,we get