Divide and Conquer Approach (DAC)

#divide #and #conquer #approach

Arvind Chauhan May 30 2021 · 2 min read
Share this

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 ?

This approach follow three steps,

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

When given problem is divided into two sub-problems

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

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

Recurrence relation for DAC
When given problem is divided into more than two sub-problems
Recurrence relation for DAC

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

    Recurrence Relation for Binary Search
    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

    Comments
    Read next