DESIGN & ANALYSIS OF ALGORITHMS
UNIT - II
2.1: Divide and conquer
2.1.1:General method
2.1.2: Applications
[Link]: Binary search
[Link]: Quick sort
[Link]:Merge sort
[Link]:Strassen’s matrix multiplication
5/2/2023 Devavarapu Sreenivasarao-II 1
CSE-C
1. Divide: Divide the problem into a no. of sub problems.
2. Conquer: conquer the sub problems by solving them recursively, if the sub
problems sizes are small enough, however, just solve the sub problems in a
straight forward manner.
3. Combine: Combine the solutions to the sub problems in to the solutions for
the original problem.
The above concept can be shown graphically as
5/2/2023 Devavarapu Sreenivasarao-II 2
CSE-C
Control Abstraction/general method for Divide and Conquer Technique
Algorithm DAndC(p)
Boolean valued function that determines whether
{
the input size is small enough that the answer can
if Small(p) then be computed without splitting
return s(p);
else
{
divide p into smaller instances p1,p2,…….,pk, k≥1;
Apply DAndC to each of these subproblems;
return Combine(DAndC(p1), DAndC(p2),……,DAndC(pk));
} Is a function that determines solution to p using
solutions to the k sub problems
}
5/2/2023 Devavarapu Sreenivasarao-II 3
CSE-C
If the size of p is n and the sizes of the k subproblems are n1,n2,….,nk
respectively, then the computing time of DAndC is described by the recurrence
relation
Where T(n) is the time for DAndC on any input of size n and
g(n) is the time to compute the answer directly for small inputs.
The function f(n) is the time for dividing p and combining the solutions to subproblems.
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 setup recurrence relation for obtaining time
for size n is
Where T(n) is the time for DAndC on any input of size n and
T(n/b) is the time for size n/b.
The function f(n) is the time for dividing problem into subproblems.
The a, b and c are constants, a is no.
5/2/2023 of sub instances
Devavarapu and and n is a power of b (i.e n=bk )
Sreenivasarao-II 4
CSE-C
Applications of Divide-and-Conquer Method:
1. Binary Search
2. Merge Sort
3. Quick Sort
4. Strassen’s Matrix Multiplication
5. Finding Maximum and Minimum element.
1. Binary Search: is a searching algorithm. In each step, the algorithm
compares the input element x with the value of the middle element in array. If
the values match, return the index of middle. Otherwise, if x is less than the
middle element, then the algorithm recurs for left side of middle element, else
recurs for right side of middle element.
5/2/2023 Devavarapu Sreenivasarao-II 5
CSE-C
[Link] search Algorithm (Iterative)
Algorithm I_Bin_Search(a, n, x)
{ //Given an array A[i:n] of elements in non decreasing order n≥0, determine whether x is present,
//and if so, return j such that x = a[j]; else return 0.
low:=1; high:=n;
while(low ≤ high) do
{
mid:=(low + high)/2;
if( x < a[mid] ) then
high:=mid-1;
else
if( x > a[mid] ) then
low:=mid + 1;
else return mid;
}
return 0;
}
5/2/2023 Devavarapu Sreenivasarao-II 6
CSE-C
Recursive Algorithm ( Divide and Conquer Technique)
Algorithm R_Bin_Search (a, i, l, x)
//Given an array a[i:l]of elements in non
//decreasing order,1≤i≤l, determine whether
//x is present, and if so, return j such that
//x=a[j]; else return 0. else
// X is the element to be searched
{
{
//Reduce p into a smaller sub problems
if ( l = i ) then // Divide the problem into smaller problems
// If small(P) mid:= ( i + l ) / 2;
// if there is one element if( x = a[mid] ) then
{ return mid;
if( x = a[i] ) then else
if ( x < a[mid] ) then
return i;
return R_Bin_Search (a, i, mid-1, x);
else else
return 0; return R_Bin_Search(a, mid+1, l, x);
}
}5/2/2023 }
Devavarapu Sreenivasarao-II 7
CSE-C
Let us select the 14 entries
-15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151.
Now x=151:
Low High Mid=(Low+high)/2 A[mid] X ? A[mid]
1 14 7 54 151 > 54
8 14 11 125 151>125
12 14 13 142 151 > 142
14 14 14 151 151 = 151
The element 151 is found
x= -14:
X=9
1 2 3 4 5 6 7
10 20 30 40 50 60 70
x= 60 write the complete step by step procedure
5/2/2023 Devavarapu Sreenivasarao-II 8
CSE-C
Time complexity of Binary Search
The time complexity for binary search technique is generally based on the
height of the binary tree.
If the no, of elements are n which is greater than 2n then the time complexity is
maximum and is a function of log n.
In successful searches, the computing time for binary search in best, average
worst cases are O(1), O(log n), O(log n) respectively.
In un successful searches, the computing time for binary search in best,
average and worst cases are O(log n) respectively.
Here we are going to find worst case computing time.
Every time we will make one comparison and divide given numbers n, into
n/2. The recurrence relation is,
5/2/2023 Devavarapu Sreenivasarao-II 9
CSE-C
5/2/2023 Devavarapu Sreenivasarao-II 10
CSE-C
2. Merge Sort
It is a sorting technique which is generally applied between two sorted arrays.
Here third array is created and the elements of both the sorted arrays are
matched, correspondingly, the third array is filled.
Hence the final third array obtained will be consisting of elements belongs to
both the arrays in a sorted order.
[Link] Case, solve the problem directly if it is small enough(only one element).
2. Divide the problem into two or more similar and smaller subproblems.
3. Recursively solve the subproblems.
4. Combine solutions to the subproblems.
5/2/2023 Devavarapu Sreenivasarao-II 11
CSE-C
Algorithm MergeSort (low, high)
// sorts the elements a[low], …, a[high] which reside in the global array a[1:n]
// into ascending order.
// Small(p) is true if there is only one element to sort. In this case the list is
// already sorted.
{
if ( low<high ) then // if there are more than one element
{
mid := (low+high)/2;
MergeSort(low,mid);
MergeSort(mid+1, high); Recursive Calls
Merge(low, mid, high);
}
} 5/2/2023 Devavarapu Sreenivasarao-II 12
CSE-C
// Merges two sub arrays of a[]. //Copy the remaining elements of L[], if there are any
// First sub array is a[l..m] while (i <= m) do
// Second sub array is a[m+1..r]
//b[ ] is a temporary global array. {
Algorithm merge(int l, int m, int r) b[k]:= L[i];
{ // Merge the temp arrays back into a[l..r] i:= i + 1;
i := l; // Initial index of first sub array k:= k + 1;
j := m+l; // Initial index of second sub array }
k := l; // Initial index of merged sub array // Copy the remaining elements of R[], if there are any
while ((i<=m) and (j<=r)) do while (j <= r) do
{ {
if (L[i] <= R[j]) then b[k]:= R[j];
{ j:= j + 1;
b[k] := L[i]; k:= k + 1;
i:=i+1; }
}
for k:= l to r do
else
{
a[k]:=b[k];
b[k] := R[j]; }
j:=j +1;
}
k:= k + 1;
} 5/2/2023 Devavarapu Sreenivasarao-II 13
CSE-C
5/2/2023 Ex:- 179, 254, 285, 310, 351,
Devavarapu 423, 450, 520, 652,861
Sreenivasarao-II 14
CSE-C
Merge-Sort Time Complexity
The best case time of an algorithm is the time required to complete the best case
input of size n, and the best case input is that input of size n for which the
algorithm runs the fastest among all possible inputs of that size.
It is worth noting that the best case doesn’t mean the smallest input, it means
the input of size n for which the algorithm runs the fastest.
The best case input for merge sort is the already sorted input.
Here we assume that the algorithm does not require the step to compare the
elements.
The best case efficiency of MERGESORT is O(n log n).
Merge sort algorithm takes constant time on just one element when the
elements are greater than one.
i.e n>1 we break down the running time as follows.
5/2/2023 Devavarapu Sreenivasarao-II 15
CSE-C
Divide: In this step, the middle of the sub array is computed, which takes
constant time, thus the time required for dividing the problem into sub problem
is O(n) = O(1).
Conquer: Two problems are solved recursively, each of size n/2. provide 2T(n/2)
to the running time.
Combine: the MERGE SORT takes O(n) time in merging. Thus the time
required to combine all the subproblems into one solution for the main problem
is C(n) = O(n).
We have,
Addition of O(n) and O(1) results in a linear function of ‘n’. i,e O(n).
If the constant time ‘C’ is used for solving the problem size 1, then we have,
5/2/2023 Devavarapu Sreenivasarao-II 16
CSE-C
Solving the above recurrence relation change of variable method
Replacing n by 2k and T(2k) = tk. We get,
T(2k ) = 2 T( 2k-1 ) + C (2k )
tk = 2 tk-1 + C 2k ------------------- (1)
Replacing k by k-1. we get,
tk-1 = 2 tk-2 + C 2k-1 ------------------- (2)
Multiplying (2) by 2 and subtracting the result from (1), we get,
tk = 2 tk-1 + C 2k
2tk-1 = 4 tk-2 + 2C 2k-1
-----------------------------
tk - 2 tk-1 = 2 tk-1 - 4 tk-2
tk - 4 tk-1 + 4 tk-2 = 0
Put tk = XK
We get the following characteristic equation
5/2/2023 Devavarapu Sreenivasarao-II 17
CSE-C
XK - 4XK-1 + 4 XK-2 = 0
X2 - 4X + 4 = 0
X2 - 2X - 2X + 4 = 0
(X - 2) (X - 2) = 0
(X - 2)2 = 0
The general equation is,
tk = (C1 + C2 k) 2k
Putting back n, we get
T(n) = C1 n + C2 n log n (since k = log2n)
T(n) = O(n log n)
The worst case of merge sort algorithm is also O(n log n)
5/2/2023 Devavarapu Sreenivasarao-II 18
CSE-C
If the time for the merging operation is proportional to n, then the computing
time for merge sort is described by the recurrence relation
Assume n=2k, then
T(n) = 2T(n/2) + C2n
= 2(2T(n/4)+C2 n/2)+Cn
= 4T(n/4)+2C2n
• Merge-Sort
…..
– Most of the work done in combining the
….. solutions.
= 2k T(1)+ kC2n – Best case takes O(n log2n) time
= C1n+C2n logn – Average case takes 0(n log2n) time
– Worst case takes O(n log2n) time
= O(n logn)
5/2/2023 Devavarapu Sreenivasarao-II 19
CSE-C
Merge-Sort Space Complexity
In merge sort for implementing recursion, we need stack. Since merge sort
splits each set into two approximately equal size subsets, the maximum depth of
the stack is proportional to log2n.
So Space complexity is O(log2n)
5/2/2023 Devavarapu Sreenivasarao-II 20
CSE-C
3. Quick Sort
Divide:
Pick any element as the pivot, e.g, the first element
Partition the remaining elements into
First Part, which contains all elements < pivot
Second Part, which contains all elements > pivot
Recursively sort First Part and Second Part.
Combine: No work is necessary since sorting is done in place.
5/2/2023 Devavarapu Sreenivasarao-II 21
CSE-C
5/2/2023 Devavarapu Sreenivasarao-II 22
CSE-C
5/2/2023 Devavarapu Sreenivasarao-II 23
CSE-C
Quick Sort Algorithm :
Algorithm QuickSort(p, q)
//Sorts the elements a[p],…..,a[q] which resides in the global array a[p:q] into ascending order;
//a[q+1] is considered to be defined and must be ≥ all the elements in a[p:q].
{
if( p< q ) then // if there are more than one element
{ // divide p into two subproblems.
j :=Partition(a, p, q+1);
// j is the position of the partitioning element.
// solve the Sub problems
QuickSort(p, j-1);
QuickSort(j+1, q);
// There is no need for combining solutions.
}
}
5/2/2023 Devavarapu Sreenivasarao-II 24
CSE-C
Algorithm Partition(a, m, p)
//with in a[m], a[m+1],….a[p-1] the elements are arranged in such a manner that if
//initially t:=a[m] then after completion a[q]:=t for some q between m and p-1, a[k]≤t
//for m ≤k ≤q and a[k] ≥ t, q<k<p. q is returned. Set a[p] = ∞.
{
v:= a[m] ;
i:=m;
j:= p;
repeat
{ Algorithm interchange ( a, i, j )
repeat {
i:= i+1; p := a[i];
until(a[i] ≥ v);
repeat a[i] := a[j];
j:=j-1; a[j] := p;
until(a[j] ≤ v);
}
if ( i < j ) then
interchange(a, i, j);
} until(i ≥ j);
a[m]:= a[j];
a[j]:=v;
return j;
} 5/2/2023 Devavarapu Sreenivasarao-II 25
CSE-C
1 2 3 4 5 6 7 8 9 10 i j Until Until If(i<j) Until
(a[i]>=v) (a[j]<=v) (i>=j)
65 70 75 80 85 60 55 50 45 +∞ 1 10 i=2 J=9 2<9 2>=9
V i j 70>=65 45<=65 Swap(7 False
2 9 True True 0,45)
65 45 75 80 85 60 55 50 70 3 8 i=3 J=8 3<8 3>=8
V i j 75>=65 50<=65 Swap(7 False
True True 5,50)
65 45 50 80 85 60 55 75 70 4 7 i=4 J=7 4<7 4>=7
V i j 80>=65 55<=65 Swap(8 False
True True 0,55)
65 45 50 55 85 60 80 75 70 5 6 i=5 J=6 5<6 5>=6
V j 85>=65 60<=65 Swap(8 False
True True 5,60)
65 45 50 55 60 85 80 75 70 6 5 i=6 J=5 6<5 6>=5
V j i 85>=65 60<=65 False True
True True Swap(
65,60)
60 45 50 55 65 85 80 75 70 Partition(a,1,4) and Partition(a,6,9)
V
5/2/2023 Devavarapu Sreenivasarao-II 26
CSE-C
1 2 3 4 5 6 7 8 9 10 i j Until Until If(i<j) Until
(a[i]>=v) (a[j]<=v) (i>=j)
60 45 50 55 65 85 80 75 70 +∞ 1 5 i=2
V i 45>=60
2 False
60 45 50 55 65 85 80 75 70 3 i=3
V i 50>=60
False
60 45 50 55 65 85 80 75 70 4 i=4
V i 55>=60
False
60 45 50 55 65 85 80 75 70 5 i=5
V i 65>=60
True
60 45 50 55 65 85 80 75 70 4 5 J=4 5<4 5>=4
V j i 55<=60 False True
True Swap(
60,55)
55 45 50 60 65 85 80 75 70 Partition(a,1,3) and Partition(a,6,9)
V
5/2/2023 Devavarapu Sreenivasarao-II 27
CSE-C
1 2 3 4 5 6 7 8 9 10 i j Until Until If(i<j) Until
(a[i]>=v) (a[j]<=v) (i>=j)
55 45 50 60 65 85 80 75 70 +∞ 1 4 i=2
V i 45>=55
2 False
55 45 50 60 65 85 80 75 70 3 i=3
V i 50>=55
False
55 45 50 60 65 85 80 75 70 4 i=4
V i 60>=55
True
55 45 50 60 65 85 80 75 70 5 J=3 4<3 4>=3
V j i 50<=55 False True
True Swap(
55,50)
50 45 55 60 65 85 80 75 70 Partition(a,1,3) and Partition(a,6,9)
V j i
5/2/2023 Devavarapu Sreenivasarao-II 28
CSE-C
1 2 3 4 5 6 7 8 9 10 i j Until Until If(i<j) Until
(a[i]>=v) (a[j]<=v) (i>=j)
50 45 55 60 65 85 80 75 70 +∞ 1 4 i=2
V i j 45>=50
2 False
50 45 55 60 65 85 80 75 70 3 i=3
V i,j 55>=50
True
50 45 55 60 65 85 80 75 70 J=2 3<2 3>=2
V j i 45<=50 False True
True Swap(
50,45)
45 50 55 60 65 85 80 75 70 Partition(a,6,9)
V
5/2/2023 Devavarapu Sreenivasarao-II 29
CSE-C
Time complexity analysis (A worst/bad case)
The worst case for quick sort occurs when the pivot is a minimum or maximum of all the elements
in the list. This can graphically represented as
C(n) = C(n-1) + 1
Or
C(n) = n+(n-1)+(n-2)+…………+2+1
But as we know
1+2+3+………..+n = n(n+1)/2 = (½)n2
Therefore C(n) = O(n2)
The5/2/2023
time complexity of worst case of Devavarapu Sreenivasarao-II
Quick sort is O(n 2) 30
CSE-C
Time complexity analysis (A Best case (split in the middle))
If the array is always portioned at the mid, then it brings the best efficiency of an algorithm.
The recurrence relation for quick sort for obtaining best case time complexity is
Time required to sort left sub array
Time required
to sort right C(n) = C(n/2) + C(n/2) + n-----------(1)
sub array
Time required for partitioning the sub array
And C(1) = 0
C(n) = 2C(n/2) + n
We assume n=2k since each time the list is divided in to two equal halves. Then (1) becomes
C(2k) = 2 C(2k/2) + 2k
= 2 C(2k-1) + 2k
Now substitute C(2k-1) = 2C(2k-2) + 2k-1
We get C(2k) = 2[2C(2k-2) + 2k-1 ] + 2k
= 22C(2k-2) + 2.2k-1 + 2k
= 22C(2k-2) + 2k + 2k
= 22C(2k-2) + 2.2k
If we substitute C(2k-2), then
5/2/2023 Devavarapu Sreenivasarao-II 31
CSE-C
= 22[2C(2k-3) +2k-2 ]+ 2.2k
= 23C(2k-3) +22.2k-2 + 2.2k
= 23C(2k-3) +2k + 2.2k
= 23C(2k-3) +3. 2k
Similarly, we can write
C(2k) = 24C(2k-4) +4. 2k
:
:
C(2k) = 2kC(2k-k) +k. 2k
= 2kC(20) +k. 2k
= 2kC(1) +k. 2k
But C(1) = 0 hence the above equation becomes
C(2k) = 2k.0 +k. 2k
Now as we assumed n = 2k we can also say k = log2n
C(n) = n.0 +k. n
= 0 +k. n
= k. n
= log2n. n
Thus it is proved that best case time complexity
5/2/2023 Devavarapu of Quick Sort is O(n.log2n)
Sreenivasarao-II 32
CSE-C
[Link]’s Matrix Multiplication
Basic Matrix Multiplication
Let A an B two n×n matrices. The product C=AB is also an n×n matrix
Algorithm matrix_mult ()
{ Then, C11=A11B11+A12B21
for i: = 1 to n do C12=A11B12+A12B22
{
for j := 1 to n do C21=A21B11+A22B21
{ C22=A21B12+A22B22
C[i,j]:=0;
for k:=1 to n do
C[i,j]:=C[i,j]+A[i,k]*B[k,j];
}
}
}
The no. of multiplications is n3 and the [Link] additions is n3.
The [Link] access of A elements is n3.
The [Link] access of B elements is n3.
The [Link] access of C elements is n2 + n3.
Time complexity of above algorithm is T(n)=O(n
5/2/2023 3)
Devavarapu Sreenivasarao-II 33
CSE-C
Each of these four equations specifies two multiplications of n/2×n/2 matrices and the
addition of their n/2×n/2 products. We can derive the following recurrence relation
for the time T(n) to multiply two n×n matrices:
To multiply 2 matrices of order 2X2, we require 8 multiplications and 4 additions.
So, T(n) = 8T(n/2) + c n2 if n>2
b if n<=2
T(n) = O(n3)
• This method is no faster than the ordinary method.
T(n)= 8T(n/2)+ c2n2
= 8(8T(n/4)+ c2(n/2)2) + c2n2
= 82 T(n/4)+ c22n2 + c2n2
=82 (8T(n/8)+ c2(n/4)2 ) + c22n2 + c2n2
=83 T(n/8)+ c24n2 + c22n2 + c2n2
:
=8kT(1)+ ………………+ c24n2 + c22n2 + c2n2
= 8log n c + c n2
2 1
=nlog28 c1 + c n2 = n3log22 c1+ cn2 =Devavarapu
5/2/2023 O(n3 ) Sreenivasarao-II 34
CSE-C
Strassen’s method
•Matrix multiplications are more expensive than matrix additions or subtractions.
•Strassen’s has discovered a way to compute the multiplication using only 7
multiplications and 18 additions or subtractions. His method involves computing 7 n×n
matrices M1,M2,M3,M4,M5,M6, and M7, then c[i,j]’s are calculated using these matrices.
Formulas for Strassen’s Algorithm Strassen’s tried to reduce the time complexity from O(n3).
M1 = (A11 + A22) X (B11 + B22) To reduce the time complexity we divide nXn matrix in to sub
M2 = (A21 + A22) X B11
matrices until we get each part as n=2.
M3 = A11 X (B12 – B22)
Example is divide 8X8 matrix in to 4 parts. Later we divide
M4 = A22 X (B21 – B11)
each part in to 4 parts again. We will continue this process until
M5 = (A11 + A12) X B22
M6 = (A21 – A11) X (B11 + B12) we get all matrices as 2X2 matrices.
M7 = (A12 – A22) X (B21 + B22)
C11=M1 + M4 - M5 + M7
C12= M3 + M5
C21= M2 + M4
C22=M1 + M3 - M2 + M6
5/2/2023 Devavarapu Sreenivasarao-II 35
CSE-C
Time Complexity:
T(n) = 7 T(n/2) + Cn2 -----------------------------(1)
T(n/2) = 7 T(n/4) + C(n/2)2 ------------------------(2)
T(n/4) = 7 T(n/8) + C(n2/16) -----------------------(3)
T(n) = 7(7 T(n/4) + C(n2/4)) + Cn2 A11 = 1, A12 = 3, A21 = 5, A22 = 7
= 72 (7 T(n/8) + C(n2/16)) + 7 C(n2/4) + Cn2 B11 = 2, B12= 4, B21 = 6, B22 = 8
= 73 T(n/23) + Cn2(7/4) 2 + Cn2(7/4) + Cn2 M1 = (A11 + A22) X (B11 + B22)
: M1 = (1 + 7) X (2 + 8) = 8 X 10 = 80
= 7k T(n/2k) + Cn2 [(7/4) k-1+(7/4) k-2 +(7/4) k-3…+ (7/4)+1] M2 = (A21 + A22) X B11
= 7k T(n/2k) + Cn2 [(7/4) k] M2 = (5 + 7) X 2 = 12 X 2 = 24
= 7k T(n/2k) + Cn2 [7 k /4 k] (since let n = 2k, k = log2n) M3 = A11 X (B12 – B22)
= 7log2n T(1) + Cn2 [7 log2n /4 log2n] (a log2n= n log2n) M3 = 1 X (4 – 8) = 1 X -4 = -4
= 7log2n + Cn2 [n log27 /n 2] M4 = A22 X (B21 – B11)
= nlog27 + Cn2 [n log27 /n 2] M4 = 7 X (6 – 2) = 7 X 4 = 28
= (1 + C) [n log27] M5 = (A11 + A12) X B22
The time complexity is O(n log27) or O(n 2.81) M5 = (1 + 3) X 8 = 4 X 8 = 32
M6 = (A21 – A11) X (B11 + B12)
C11=M1 + M4 - M5 + M7 C21= M2 + M4
M6 = (5 – 1) X (2 + 4) = 4 X 6 = 24
C11=80 + 28 - 32 + -56 = 20 C21= 24 + 28 = 52
M7 = (A12 – A22) X (B21 + B22)
C12= M3 + M5 C22=M1 + M3 - M2 + M6
5/2/2023 Devavarapu Sreenivasarao-II M7 = (3 – 7) X (6 + 8) = -4 X1436
= -56
C12= -4 + 32 = 28 C22=80 + -4 - 24 + 24 = 76 CSE-C
Give an example showing that quick sort is not a stable sorting algorithm.
Example is Bubble sort.
Example is Quick sort.
5/2/2023 Devavarapu Sreenivasarao-II 37
CSE-C