DIVIDE AND CONQUER - By Ohm Patel
ALGORITHMS
BINARY SEARCH
• The most common way to find an element in a given array is the linear search.
• Linear search follows a brute force approach and iterates through all the array
elements until it finds the one being searched for.
• This is an inefficient way of dealing with the problem as the algorithm’s time
complexity is O(N).
• To make searching more efficient we can use binary search which is a divide and
conquer algorithm.
BINARY SEARCH
• Binary search only works on a sorted array.
• We divide the sorted array into 2 equal parts and note the value of the center
element.
• Then we compare this element to the one that is being searched for.
• If the center element is greater than the element we are looking for, we can discard
the second half of the array as all the values in the second part will be greater than
what we need.
• If the center element is smaller than the element we are looking for, we can discard
the first half of the array as all the values in the first part will be smaller than what
we need.
BINARY SEARCH
• We repeat this process until the start pointer and end pointer of our array become
the same, hence pointing to the element that we are looking for.
• The time complexity of this algorithm is O(logn) which is significantly better than that
of linear search.
BINARY SEARCH - EXAMPLE
QUICK SORT
•It is a sorting algorithm.
•It is a recursive algorithm and follows a divide-and-conquer approach.
•The average case time complexity of this algorithm is O(nlogn).
•It picks an element as a pivot and partitions the given array around the
picked pivot.
STEPS:
• Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array into
two sub-arrays such that each element in the left sub-array is less than or equal to the pivot
element and each element in the right sub-array is larger than the pivot element.
• Conquer: Recursively, sort two subarrays with Quicksort.
• Combine: Combine the already sorted array.
• Pivot can be random, i.e. select the random pivot from the given array.
• Pivot can either be the rightmost element or the leftmost element of the given array.
• Select median as the pivot element.
EXAMPLE
EXAMPLE
EXAMPLE
MERGE SORT
•The Merge Sort algorithm is a sorting algorithm that is based on the Divide and
Conquer paradigm.
• The array is initially divided into two equal halves and then they are combined in a
sorted manner.
• Divide: Then the array is further divided into smaller pieces until all the elements are
separated.
• Conquer: When merging the separated element back together, we put the smaller
elements before the larger ones.
• Combine: Finally, when both halves are sorted, the merge operation is
applied.
MERGE SORT - EXAMPLE
MERGE SORT - EXAMPLE
MASTER THEOREM - EXAMPLE
STRASSEN MULTIPLICATION
• It is a method to optimise normal matrix multiplication.
• void multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
•The above code is of normal matrix multiplication and has three nested loops iterating from
0 to n each.
•The time complexity of normal matrix multiplication is O(n3).
DAC FOR MATRIX MULTIPLICATION
• Following is simple Divide and Conquer method to multiply two square matrices.
- Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below
diagram.
- Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.
• We need to do 8 multiplications on a matrix that is on (n/2,n/2) size, for the above
step.
•We also have to perform 4 matrix additions (ae + bg, af + bh, ce + dg and cf +
dh), meaning that we have to add 4 elements of each matrix (for instance, ae and bg
both have 4 elements each.)
•Hence the total time taken is T(n) = 8T(n/2) + n 2. Using master’s theorem the time
complexity is O(n3).
STRASSEN’S METHOD
• To reduce the time complexity of the problem, we have to reduce the number of
multiplications required.
• To do this, Strassen gave his own formulae to find the resultant matrix of the product
of 2 matrices.
• His formulae involved only 7 multiplications instead of 8.
• Even though the number of additions and subtractions increased, they do not
contribute majorly to the time complexity of the problem.
• Since his method has 7 multiplications and also follows the divide and conquer
approach, the new recurrence relations is T(n) = 7T(n/2) + n 2.
• Using master’s theorem, we get the time complexity of this algorithm as O(n 2.81).
STRASSEN’S FORMULAE
For matrices C=A.B, the formulae as as follows:
ANALYSIS OF DAC RUNTIME
RECURRENCE RELATIONS
• A recurrence relation is a mathematical relation that describes how a recursive
function works.
• To find the time complexity of a recursive algorithm through its recurrence relation,
we can use any 1 of 3 methods:
1. Recursive Tree method
2. Back substitution method/ induction method
3. Master Theorum
RECURSIVE TREE METHOD
RECURSIVE TREE METHOD
BACK SUBSTITUTION METHOD
