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
if Small(P) then return S(P);
Divide P into smaller problems P1,P2…….Pk, k≥1;
Apply DAC to each of these sub problems;
RECURRENCE RELATION FOR DIVIDE & CONQUER APPROACH
f(n)=Some amount of time required for dividing & combining problem n.
APPLICATIONS OF DAC
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
Binary Search(a, i, j, X)
if( i == j )
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