---

Introduction

---

Introduction

The Divide-and-Conquer strategy suggests splitting the n inputs into 'k' distinct subsets, yielding 'k' sub problems. If the sub problems are still relatively large, then the divide-and-conquer strategy can possibly be reapplied. These sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole.

General Method

i) Divided into smaller subproblems.
ii) These subproblems are solved independently.
iii) Combining all the solutions of subproblems into a solution of the whole.

If the sub problems are still relatively large, then divide-and-conquer is reapplied. The generated sub problems are usually of same type as the original problem. Hence recursive algorithm are used.

Algorithm:

Algorithm DAndC(P)
{
	if small(P) then 
		return S(P);
	else
	{
		divide P into smaller instances
        P1, P2 .. Pk, k>=1;
		Apply DAndC to each of these sub problems;
		return combine (DAndC(P1), DAndC(P2),...,DAndC(Pk));
	}
}

The computing time of above procedure of divide and conquer is given by the recurrence relation.

$$T(n)=\{\begin{array}{ll}g(n)& \mathrm{n\; small}\\ T(n_1)+T(n_2)+\; ...\; +T(n_{\mathrm{k}})+f(n)& \mathrm{otherwiser}\end{array}$$

Where T(n) is the time for divide and conquer of size n. The g(n) is the computing time required to solve small inputs. The F(n) is the time required in dividing problem P and combining the solution to sub problems.

The complexity of many divide-and-conquer algorithms is given by recurences of the form

$$T(n)=\{\begin{array}{ll}T(n)& n=0\\ \mathrm{aT}(\mathrm{n/b})+f(n)& n>0\end{array}$$
where a and b are known constants. We assume that T(1) is known and n is power of b( i.e., n=b^k ).


Example:

Consider the case in which a=2 and b=2. Let T(n)=2 and f(n)=n. we have

$T(n)=\mathrm{2T}(\mathrm{n/2})+n$
$.=2[\mathrm{2T}(\mathrm{n/4})+\mathrm{n/2}]+n$
$.=\mathrm{4T}(\mathrm{n/4})+\mathrm{2n}$
$.=4[\mathrm{2T}(\mathrm{n/8})+\mathrm{n/4}]+\mathrm{2n}$
$.=8T(\mathrm{n/8})+\mathrm{3n}$
           *
           *
           *

In general, we see that

$T(n)=2^{\mathrm{i}}T({\mathrm{n/2}}^{\mathrm{i}})+\mathrm{in}$ ,  for any  ${\log }_{2}n\ge i\ge 1$

in particular, $T(n)=2^{{\log }_{2}n}T({\mathrm{n/2}}^{{\log }_{2}n})+n{\log }_{2}n$ corresponding to the choice of $i={\log }_{2}n$

Thus, $T(n)=nT(1)+n{\log }_{2}n=n{\log }_{2}n+\mathrm{2n}$