# Divide and Conquer Approach (DAC)

Arvind Chauhan May 30 2021 · 2 min read

WHY WE USE DIVIDE & CONQUER (DAC) APPROACH ?

Many algorithms are recursive in nature. That means, for solving a particular problem they call themselves recursively one or more times. All these algorithms follow the Divide & Conquer approach.

WHAT IS DIVIDE & CONQUER (DAC) APPROACH ?

1. Divide the original problem into a set of sub problems.

2. Solve every sub problem individually, recursively.

3. Finally, the solutions obtained by the sub problems are combined to create solution to the original problem.

CONTROL ABSTRACTION OF DIVIDE & CONQUER APPROACH

DAC(P)

{

if Small(P) then return S(P);

else

{

Divide P into smaller problems P1,P2…….Pk, k≥1;

Apply DAC to each of these sub problems;

return(Combine(DAC(P1),DAC(P2)……DAC(Pk)));

}

}

RECURRENCE RELATION FOR DIVIDE & CONQUER APPROACH

T(n)=T(n/2)+T(n/2)+f(n)

f(n)=Some amount of time required for dividing & combining problem n.

APPLICATIONS OF DAC

• Binary Search
• Merge Sort
• Quick Sort
• Strassen’s Matrix Multiplication
• BINARY SEARCH

A Binary Search algorithm is a technique for finding a particular value in a sorted list.

Input:-    10,20,30,40,50,60,70, X

Output:-   Position of X

Algorithm==>

Binary Search(a, i, j, X)

{

if( i == j )

{

if(a[i]==X)

return(i);

else

return(-1);

}

else

{

mid=(i+j)/2;

if(a[mid]==X)

return(mid);

else

{

if(a[mid]>X)

Binary Search(a,i,mid-1,X);

else

Binary Search(a,mid+1,j,X);

}

}

}

RECURRENCE RELATION FOR BINARY SEARCH

TIME COMPLEXITY OF BIN ARY SEARCH

Best Case Time Complexity = O(1)

Worst Case Time Complexity = O(log n)

Average Case Time Complexity = O(log n