= 2^k-1+2^k-2

= 2^k/2+2^k-2
= n/2+n-2
= (n+2n)/2)-2
T(n)=(3n/2)-2

*Note that (3n/3)-3 is the best-average, and worst-case no. of comparisons when ‘n’ is a power of 2.

4.4.QUICK SORT

 The divide-and-conquer approach can be used to arrive at an efficient sorting method different
from merge sort.
 In merge sort, the file a[1:n] was divided at its midpoint into sub arrays which were
independently sorted & later merged.
 In Quick sort, the division into 2 sub arrays is made so that the sorted sub arrays do not need to
be merged later.
 This is accomplished by rearranging the elements in a[1:n] such that a[I]<=a[j] for all I
between 1 & n and all j
between (m+1) & n for some m, 1<=m<=n.
 Thus the elements in a[1:m] & a[m+1:n] can be independently sorted.

 No merge is needed. This rearranging is referred to as partitioning.

 Function partition of Algorithm accomplishes an in-place partitioning of the elements of

a[m:p-1]
 It is assumed that a[p]>=a[m] and that a[m] is the partitioning element. If m=1 & p-1=n, then
a[n+1] must be
 defined and must be greater than or equal to all elements in a[1:n]
 The assumption that a[m] is the partition element is merely for convenience, other choices for
the partitioning
element than the first item in the set are better in practice.
 The function interchange (a,I,j) exchanges a[I] with a[j].

73
Algorithm: Partition the array a[m:p-1] about a[m]

Algorithm Partition(a,m,p)
//within a[m],a[m+1],…..,a[p-1] the elements
// are rearranged 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 for q<k<p. q is returned
//Set a[p]=infinite.
{
v=a[m];I=m;j=p;
repeat
{
repeat
I=I+1;
until(a[I]>=v);
repeat
j=j-1;
until(a[j]<=v);
if (I<j) then interchange(a,i.j);
}until(I>=j);
a[m]=a[j]; a[j]=v;
retun j;
}

Algorithm Interchange(a,I,j)
//Exchange a[I] with a[j]
{
p=a[I];
a[I]=a[j];
a[j]=p;

74
 int p;
p= a[I];
a[I]=a[j];
a[j]=p;
}

Output:
Enter the no. of elements 5
Enter the array elements
3
8
1
5
2
The sorted elements are,
1
2
3
5
8

4.5.MERGE SORT

 As another example divide-and-conquer, we investigate a sorting algorithm that has the nice
property that is the worst case its complexity is O(n log n)
 This algorithm is called merge sort
 We assume throughout that the elements are to be sorted in non-decreasing order.
 Given a sequence of ‘n’ elements a[1],…,a[n] the general idea is to imagine then split into 2
sets a[1],…..,a[n/2] and a[[n/2]+1],….a[n].
 Each set is individually sorted, and the resulting sorted sequences are merged to produce a
single sorted sequence of ‘n’ elements.
 Thus, we have another ideal example of the divide-and-conquer strategy in which the splitting
is into 2 equal-sized sets & the combining operation is the merging of 2 sorted sets into one.

77
Algorithm For Merge Sort:
Algorithm MergeSort(low,high)
//a[low:high] is a global array to be sorted
//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
{
//Divide P into subproblems
//find where to split the set
mid = [(low+high)/2];
//solve the subproblems.
mergesort (low,mid);
mergesort(mid+1,high);
//combine the solutions .
merge(low,mid,high);
}
}

Algorithm: Merging 2 sorted subarrays using auxiliary storage.

Algorithm merge(low,mid,high)
//a[low:high] is a global array containing
//two sorted subsets in a[low:mid]
//and in a[mid+1:high].The goal is to merge these 2 sets into
//a single set residing in a[low:high].b[] is an auxiliary global array.
{
h=low; I=low; j=mid+1;
while ((h<=mid) and (j<=high)) do
{
if (a[h]<=a[j]) then
{
b[I]=a[h];

78
 h = h+1;
}
else
{
b[I]= a[j];
j=j+1;
}
I=I+1;
}
if (h>mid) then
for k=j to high do
{
b[I]=a[k];
I=I+1;
}
else
for k=h to mid do
{
b[I]=a[k];
I=I+1;
}
for k=low to high do a[k] = b[k];
}

 Consider the array of 10 elements a[1:10] =(310, 285, 179, 652, 351, 423, 861, 254, 450, 520)
 Algorithm Mergesort begins by splitting a[] into 2 sub arrays each of size five (a[1:5] and
a[6:10]).
 The elements in a[1:5] are then split into 2 sub arrays of size 3 (a[1:3] ) and 2(a[4:5])
 Then the items in a a[1:3] are split into sub arrays of size 2 a[1:2] & one(a[3:3])
 The 2 values in a[1:2} are split to find time into one-element sub arrays, and now the merging
begins.

79
 It is easy to see that if s^k<n<=2^k+1, then T(n)<=T(2^k+1). Therefore,
T(n)=O(n log n)

4.6.STRASSEN’S MATRIX MULTIPLICAION

1. Let A and B be the 2 n*n Matrix. The product matrix C=AB is calculated by using the
formula,

C (i ,j )= A(i,k) B(k,j) for all ‘i’ and and j between 1 and n.

2. The time complexity for the matrix Multiplication is O(n^3).

3. Divide and conquer method suggest another way to compute the product of n*n matrix.

4. We assume that N is a power of 2 .In the case N is not a power of 2 ,then enough rows and
columns of zero
can be added to both A and B .SO that the resulting dimension are the powers of two.

5. If n=2 then the following formula as a computed using a matrix multiplication operation for
the elements of
A & B.

6. If n>2,Then the elements are partitioned into sub matrix n/2*n/2..since ‘n’ is a power of 2
these product can be recursively computed using the same formula .This Algorithm will
continue applying itself to smaller sub
matrix until ‘N” become suitable small(n=2) so that the product is computed directly .
7. The formula are

A11 A12 B11 B12 C11 C12

* =
A21 A21 B21 B22 C21 C22

C11 = A11 B11 + A12 B21

C12 = A11 B12 + A12 B22
C21 = A21 B11 + A22 B21
C22 = A21 B12 + A22 B22

81
For EX:
2222 1 1 11
4*4= 2222 1 1 11
2222 * 1 1 11
2222 1 11 1

The Divide and conquer method

2 2 2 2 1 1 1 1 4 4 4 4
2 2 2 2 * 1 1 1 1 = 4 4 4 4
2 2 2 2 1 1 1 1 4 4 4 4
2 2 2 2 1 1 1 1 4 4 4 4

8. To compute AB using the equation we need to perform 8 multiplication of n/2*n/2 matrix

and from 4 addition of n/2*n/2 matrix.
9. Ci,j are computed using the formula in equation 4
10. As can be sum P, Q, R, S, T, U, and V can be computed using 7 Matrix multiplication and 10
addition or subtraction.
11. The Cij are required addition 8 addition or subtraction.
T(n)= b n<=2 a &b are
7T(n/2)+an^2 n>2 constant

Finally we get T(n) =O( n ^log27)

Example

4 4 4 4
*
4 4 4 4

P=(4*4)+(4+4)=64
Q=(4+4)4=32
R=4(4-4)=0
S=4(4-4)=0
T=(4+4)4=32
U=(4-4)(4+4)=0
V=(4-4)(4+4)=0
C11=(64+0-32+0)=32
C12=0+32=32

82
Example
Suppose we have in a country the following coins are available :
Dollars(100 cents)
Quarters(25 cents)
Dimes( 10 cents)
Nickel(5 Cents)
Pennies(1 cent)
Our aim is paying a given amount to a customer using the smallest possible number of coins.
For example if we must pay 276 cents possible solution then,
 1 doll+7 q+ 1 pen9 coins
 2 doll +3Q +1 pen6 coins
 2 doll+7dim+1 nic +1 pen11 coins.

4.8.JOB SCHEDULING WITH DEAD LINES

The problem is the number of jobs, their profit and deadlines will be given and we have to find a
sequence of job, which will be completed within its deadlines, and it should yield a maximum
profit.
Points To remember:
To complete a job, one has to process the job or a action for one unit of time. Only one machine is
available for processing jobs. A feasible solution for this problem is a subset of j of jobs such that
each job in this subject can be completed by this deadline.If we select a job at that time ,
Since one job can be processed in a single m/c. The other job has to be in its waiting state until
the job is completed and the machine becomes free.
So the waiting time and the processing time should be less than or equal to the dead line of the
job.
ALGORITHM:
Algorithm JS(d,j,n)
//The job are ordered such that p[1]>p[2]…>p[n]
//j[i] is the ith job in the optimal solution
// Also at terminal d [ J[ i]<=d[ J {i+1],1<i<k
{
d[0]= J[0]=0;
J[1]=1;

85
K=1;
For I =1 to n do
{ // consider jobs in non increasing order of P[I];find the position for I and check feasibility
insertion
r=k;
while((d[J[r]]>d[i] )and
(d[J[r]] = r)do r =r-1;
if (d[J[r]]<d[I])and (d[I]>r))then
{
for q=k to (r+1) step –1 do J [q+1]=j[q]
J[r+1]=i;
K=k+1;
}
}
return k;
}
Example :
1. n=5 (P1,P2,…P5)=(20,15,10,5,1)
(d1,d2….d3)=(2,2,1,3,3)

Feasible solution Processing Sequence Value

(1) (1) 20
(2) (2) 15
(3) (3) 10
(4) (4) 5
(5) (5) 1
(1,2) (2,1) 35
(1,3) (3,1) 30
(1,4) (1,4) 25
(1,5) (1,5) 21
(2,3) (3,2) 25
(2,4) (2,4) 20

86
(2,5) (2,5) 16
(1,2,3) (3,2,1) 45
(1,2,4) (1,2,4) 40

The Solution 13 is optimal

n=4 (P1,P2,…P4)=(100,10,15,27)
(d1,d2….d4)=(2,1,2,1)

Feasible solution Processing Sequence Value

(1,2) (2,1) 110
(1,3) (1,3) 115
(1,4) (4,1) 127
(2,3) (9,3) 25
(2,4) (4,2) 37
(3,4) (4,3) 42
(1) (1) 100
(2) (2) 10
(3) (3) 15
(4) (4) 27
The solution 3 is optimal.

4.9.KNAPSACK PROBLEM
we are given n objects and knapsack or bag with capacity M object I has a weight Wi where I
varies from 1 to N.
The problem is we have to fill the bag with the help of N objects and the resulting profit has to be
maximum.
Formally the problem can be stated as
Maximize xipi subject to XiWi<=M
Where Xi is the fraction of object and it lies between 0 to 1.
There are so many ways to solve this problem, which will give many feasible solution for which we
have to find the optimal solution. But in this algorithm, it will generate only one solution which is
going to be feasible as well as optimal. First, we find the profit & weight rates of each and every
object and sort it according to the descending order of the ratios. Select an object with highest p/w

87