__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 P
_{1},P_{2},.......P_{k}. - 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 n
_{1},n_{2},....n_{k} respectively. - Then ,the computing time of divide and conquer is described by the recurrence relation.

__Algorithm:__

__Control Abstraction for Divide and Conquer__

__Algorithm DNC(P)__

{

if P then return S(P)

else

{

divide P into smaller instances P_{1},P_{x},....P_{k}.

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

_{1}),DNC(P_{2}),.....DNC(AC)}

}

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

__Solution__:

Let ,n=2^{k} and T(2^{k})=t_{k}

⇒T(2^{k})=4T(2^{k-1})+2^{k}

⇒t_{k}=4t_{k-1}+2^{k} ......... (i)

Replacing k by k-1 we get,

⇒t_{k-1}=4t_{k-2}+2^{k-1} ................(ii)

Multiply eq(ii) by 2 ,we get

⇒2t_{k-1}=8t_{k-2}+2^{k} ................(iii)

Substract (iii) from (i) ,we get

⇒t_{k}-2t_{k-1}=4t_{k-1}-8t_{k-2}

⇒t_{k}-6t_{k-1}+8t_{k-2}=0

Let,t_{k}=x^{k}

⇒x^{k}-6x^{k-1}+8x^{k-2}=0

or

⇒x^{2}-6x+8=0

⇒(x-2)(x-4)=0

⇒t_{k}=c_{1}2^{k}+c_{2}4^{k}

Putting back n, we get

⇒T(n)=c_{1}n+c_{2}n^{2 }

Therefore,T(n)£O(n^{2})

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

__Solution__:

Recurrence relation,T(n)=4T(n/2)+n^{2}

Since n>1 and is power of 2 ,

put n=2^{k} and T(2^{k})=t_{k} to get,

⇒t_{k}=4t_{k-1}+2^{2}^{k} ....... (i)

And replacing k by k-1 ,we get

⇒t_{k-1}=4t_{k-2}+2^{2(k-1)} ........(ii)

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

⇒t_{k}-4t_{k-1}=4t_{k-1}-16t_{k-2}

or

⇒ t_{k}-8t_{k-1}+16t_{k-2}=0

Putting t_{k}=x^{k},we get

⇒x^{k}-8x^{k-1}+16x^{k-2}=0

⇒ x^{2}-8x+16=0

⇒(x-4)^{2}_{=0}

Therefore,T(n)£O(n^{2} logn)

_{ }