Divide and Conquer Algorithm | Divide and Conquer

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 Algorithm

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

  1. Divide the problem S in sub problems like S1, S2, … , Sn.
  2. Solve the sub problems independently.
  3. 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(n1) + T(n2) + ….. + T(nr) + 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:

  1. Fibonacci Search
  2. Binary Search
  3. Merge Sort
  4. Quick Sort
  5. Matrix Multiplication

 

Topic : Divide and Conquer Algorithm | Divide and Conquer

Leave a Reply