## Divide and conquer

**Divide and Conquer Algorithm General method**

Usually recursive algorithms typically follow a divide-and-conquer approach: they break the problem into several sub problems that are similar to the original problem but smaller in size, solve the sub problems recursively, and then combine these solutions to create a solution to the original problem

**Divide -and- conquer** is a general algorithm design paradigm:

- Divide the problem
*S*in sub problems like*S*1*, S*2, … , Sn. - Solve the sub problems independently.
- Combining all the solutions of sub problems into a solution for
*S.*

If the sub problems are large then divide and conquer is reapplied.

The generated sub problems are generally of same type as the original problem. Hence recursive algorithms are used in divide and conquer is strategy.

The base cases for the recursion are sub problems of constant size.

**Control Abstraction**: Control abstraction for divide and conquer method is given below:

**Divide and Conquer Algorithm**

Algorithm DAC(P) { if(small(P)) then return S(P); else { Divide P into smaller instances P1,P2,…Pn where n≥1 Call DAC((P) to each of these sub problems return combine(DA({P1),DAC(P2), …, DAC(Pn)); } }

General **Time complexity Analysis** of algorithm **Divide and Conquer** is given by the recurrence relation.

T(n) = g(n) if n is small

**T(n) = T(n _{1}) + T(n_{2}) + ….. + T(n_{r}) + F(n) when n is large**

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

If we want to divide a problem of size n into a size of n/b taking f(n) time to divide and combine, then we can set up recurrence relation for obtaining time for size n is

**T(n) = aT(n/b) +f(n)**

Where** T(n)** – Time for size n

**a** – no.of sub problems

**n/b** – Time for size sub problem n/n

**f(n)** – Time required for dividing the problem into sub problem.

The above equation is called general divide and conquer recurrence. The order of growth of T(n) depends upon the constants a, b and order of growth function f(n).

Some of the applications which are based on **Divide and conquer approach** are:

**Fibonacci Search****Binary Search****Merge Sort****Quick Sort****Matrix Multiplication**

Topic : Divide and Conquer Algorithm | Divide and Conquer