UNIT II

BRUTE FORCE AND DIVIDE-AND-CONQUER

Brute Force – Computing an – String Matching - ExhaustiveSearch - Travelling

Salesman Problem - Knapsack Problem - Assignment problem. Divide and
Conquer Methodology – Multiplication of Large Integers – Strassen’s matrix
Multiplication - Closest-Pair and Convex-Hull Problems - Decrease and Conquer:
Topological Sorting - Transform and Conquer: Presorting -Heaps and Heap Sort

Content beyond Syllabus

Binary Search – Merge sort – Quick sort – Insertion Sort- Selection Sort

 Define Brute force

 Write the brute force algorithm for string matching [Part A -APR/MAY 2019]
 What is brute force method [Part A -NOV/DEC 2019]
 State the convex Hull problem [Part A -NOV/DEC 2019]
 What is the convex hull problem explain the brute force approach to solve the
convex hull with an example. Derive the time complexity [Part B- APR/MAY
2019]

1. BRUTE FORCE

Brute force is a straightforward approach to solving a problem, usually

directly based on the problem’s statement and definitions of the concepts
involved. For e.g. the algorithm to find the gcd of two numbers.

Brute force approach is not an important algorithm design strategy for the
following reasons:

First, unlike some of the other strategies, brute force is applicable to a very
wide varietyof problems. It’s used for many elementary but algorithmic tasks
such as computing the sum of n numbers, finding the largest element in a list
and so on.
Second, for some problem it yields reasonable algorithms of at least some
practical valuewith no limitation on instance size.

Third, the expense of designing a more efficient algorithm if few instances to

be solvedand with acceptable speed for solving it.

Fourth, even though it is inefficient, it can be used to solve small-instances of a

problem.
Last, it can serve as an important theoretical or educational propose.

 What is the closest pair problem? [Part A MAY/JUNE 2016]

 Give the General Strategy of Divide and Conquer Method. [Part A
MAY/JUNE 2016]

CLOSEST PAIR AND CONVEX HULL PROBLEMS

CLOSEST-PAIR PROBLEM

The closest-pair problem calls for finding the two closest points in a set of n
points. It is the simplest of a variety of problems in computational geometry
that deals with proximity of points in the plane or higher-dimensional spaces.

Points in question can represent such physical objects as airplanes or post

offices as well as database records, statistical samples, DNA sequences, and so
on.

An air- traffic controller might be interested in two closest planes as the most
probable collision candidates. A regional postal service manager might need a
solution to the closest pair problem to find candidate post-office locations to
be closed.

One of the important applications of the closest-pair problem is cluster

analysis in statistics. Based on n data points, hierarchical cluster analysis
seeks to organize them in a hierarchy of clusters based on some similarity
metric.

For numerical data, this metric is usually the Euclidean distance; for text and
other non numerical data, metrics such as the Hamming distance are used. A
bottom-up algorithm begins with each element as a separate cluster and
merges them into successively larger clusters by combining the closest pair of
clusters.

For simplicity, we consider the two-dimensional case of the closest-pair

problem. We assume that the points in question are specified in a standard
fashion by their (x, y) Cartesian coordinates and that the distance between
two points pi(xi,yi) and pj(xj, yj ) is the standard Euclidean distance

d(pi, pj ) = (xi− xj )2 + (yi− yj )2

The brute-force approach to solving this problem leads to the following

obvious algorithm: compute the distance between each pair of distinct points
and find a pair with the smallest distance. Of course, we do not want to
compute the distance between the same pair of points twice. To avoid doing
so, we consider only the pairs of points (pi, pj ) for which i < j.

Pseudocode below computes the distance between the two closest points;
getting the closest points themselves requires just a trivial modification.

ALGORITHM BruteForceClosestPair(P )

//Finds distance between two closest points in the plane by brute

force
//Input: A list P of n (n ≥ 2) points p1(x1, y1), . . . , pn(xn, yn)
//Output: The
distance between
the closest pair of
points d←∞
for i ←1 to n − 1

do

for j ←i + 1 to n

do
 d ←min(d, sqrt((xi− xj )2 + (yi− yj )2)) //sqrt is square root
return d

The basic operation of the algorithm is computing the square root. In the age
of electronic calculators with a square-root button, one might be led to believe
that computing the square root is as simple an operation as, say, addition or
multiplication.

Of course, it is not. For starters, even for most integers, square roots are
irrational numbers that therefore can be found only approximately.

Moreover, computing such approximations is not a trivial matter. But, in

fact, computing square roots in the loop can be avoided!

The trick is to realize that can simply ignore the square-root function and
compare the values (xi− xj )2 + (yi− yj )2 themselves.

Then the basic operation of the algorithm will be squaring a number. The
number of times it will be executed can be computed as follows: Of course,
speeding up the innermost loop of the algorithm could only decrease the
algorithm’s running time by a constant but it cannot improve its asymptotic
efficiency class.

CONVEX-HULL PROBLEM

On to the other problem—that of computing the convex hull. Finding the

convex hull for a given set of points in the plane or a higher dimensional space
is one of the most important—some people believe the most important—
problems in computational geometry.

This prominence is due to a variety of applications in which this problem

needs to be solved, either by itself or as a part of a larger task. Several such
applications are based on the fact that convex hulls provide convenient
approximations of object shapes and data sets given.
For example, in computer animation, replacing objects by their convex hulls
speeds up collision detection; the same idea is used in path planning for Mars
mission rovers.
Convex hulls are used in computing accessibility maps produced from
satellite images by Geographic Information Systems. They are also used for
detecting outliers by some statistical techniques.

An efficient algorithm for computing a diameter of a set of points, which is the

largest distance between two of the points, needs the set’s convex hull to find
the largest distance between twoof its extreme points (see below).

Finally, convex hulls are important for solving many optimization problems,
because their extreme points provide a limited set of solution candidates.

A set of points (finite or infinite) in the plane is called convex if for any two
point’s p and q in the set, the entire line segment with the endpoints at p and
q belongs to the set. All the sets depicted are convex, and so are a straight line,
a triangle, a rectangle, and, more generally, any convex polygon,1 a circle, and
the entire plane.

On the other hand, the sets, any finite set of two or more distinct points, the
boundary of any convex polygon, and a circumference are examples of sets
that are not convex. Now we are ready for the notion of the convex hull.

Intuitively, the convex hull of a set of n points in the plane is the smallest
convex polygon that contains all of them either inside or on its boundary

Imagine that the points in question are represented by nails driven into a
large sheet of plywood representing the plane. Take a rubber band and
stretch it to include all the nails, then let it snap into place.

The convex hull is the area bounded by the snapped rubber band A formal
definition of the convex hull that is applicable to arbitrary sets, including sets
of points that happen to lie on the same line, follows.
The convex hull of a set S of points is the smallest convex set containing S.
(The “smallest” requirement means that the convex hull of S must be a subset
of any convex set containing S.)

If S is convex, its convex hull is obviously S itself. If S is a set of two points, its
convex hull is the line segment connecting these points. If S is a set of three
points not on the same line, its convex hull is the triangle with the vertices at
the three points given; if the three points do lie on the same line, the convex
hull is the line segment with its endpoints at the two points that are farthest
apart.

EXHAUSTIVE SEARCH

It is a straightforward method used to solve problems of combinatorial

problems. It generates each and every element of the problem’s domain,
selecting based on satisfying the problem’s constraints and then finding a
desired element (eg., maximization or minimization of desired
characteristics).

 State the travelling salesman problem. Elaborate the steps in

solving the travelling salesman problem using brute force
approach. [Part B -NOV/DEC 2019]
 Write the algorithm to find the closest pair of points using divide
and conquer and explain it with an example. Derive the worst case
and average case time complexity. [Part B -NOV/DEC 2019]

3. TRAVELING SALESMAN PROBLEM

The problem asks to find the shortest tour through a given set of n cities that
visits each city exactly once before returning to the city where it started.

The problem can be stated as the problem of finding the shortest Hamiltonian
circuit of the graph-which is a weighted graph, with the graph’s vertices
representing the cities and the edge weights specifying the distance.

Hamiltonian circuit is defined as a cycle that passes thru all the vertices of
the graph exactly once.
The Hamiltonian circuit can also be defined as a sequence of n+1 adjacent
vertices vi0, vi1,… Vin-1, vi0, where the first vertex of the sequence is the
same as the last one while all other n-1 verticesare distinct.

Obtain the tours by generating all the permutations of n-1 intermediate cities,
compute the tour lengths, and find the shortest among them.

Consider the condition that the vertex B precedes C then, the total no of
permutations will be (n-1)! /2, which is impractical except for small values of
n. On the other hand, if the starting vertex is not considered for a single vertex,
the number of permutations will be even large for n values.

 Outline the Knapsack Problem[Part A -NOV/DEC 2019]

3.1. KNAPSACK PROBLEM

The problem states that: given n items of known weights w1,w 2, … wn and
values v1, v2,…, vn and a knapsack of capacity w, find the most valuable subset
of the items that fit into the knapsack.

Eg consider a transport plane that has to deliver the most valuable set of
items to a remote location withoutexceeding its capacity.

Example:
W=10, w1,w2, w3, w4 = { 7,3,4,5 } and v1,v2, v3, v4 = { 42,12,40,25 }

Subset Total weight Total value

Ø 0 0
{1} 7 $42
{2} 3 $12
{3} 4 $40
{4} 5 $25
{ 1,2 } 10 $54
{ 1,3 } 11 Not feasible
{ 1,4 } 12 Not feasible
 { 2,3 } 7 $52
{ 2,4 } 8 $37
{ 3,4 } 9 $65
{ 1,2,3 } 14 Not feasible
{ 1,2,4 } 15 Not feasible
{ 1,3,4 } 16 Not feasible
{ 2,3,4 } 12 Not feasible
{ 1,2,3,4 } 19 Not feasible

This problem considers all the subsets of the set of n items given, computing
the total weight of each subset in order to identify feasible subsets (i.e., the
one with the total weight not exceeding the knapsack capacity) and finding
the largest among the values, which is an optimal solution.

The number of subsets of an n-element set is 2n the search leads to a Ω(2n)

algorithm, which is not based on the generation of individual subsets.

Thus, for both TSP and knapsack, exhaustive search leads to algorithms that
are inefficient on every input. These two problems are the best-known
examples of NP- hard problems.

No polynomial- time algorithm is known for any NP-hard problem. The two
methods Backtracking and Branch & bound enable us to solve this problem in
less than exponential time.

4. ASSIGNMENT PROBLEM

The problem is: given n people who need to be assigned to execute n jobs,
one person per job. The cost if the ith person is assigned to the jth job is a
known quantity c[i,j] for each pair i,j=1,2,….,n. The problem is to find an
assignment with the smallest total cost.

Job1 Job2 Job3 Job4

Person1 9 2 7 8
Person2 6 4 3 7
Person3 5 8 1 8
 Person4 7 6 9 4

9 2 7 8 < 1,2,3,4 > cost = 9 + 4 + 1 + 4 = 18

6 4 3 7 < 1,2,4,3 > cost = 9 + 4 + 8 + 9 = 30
C= 5 8 1 8 < 1,3,2,4 > cost = 9 + 3 + 8 + 4 = 24
7 6 9 4 < 1,3,4,2 > cost = 9 + 3 + 8 + 6 = 26 etc.

From the problem, obtain a cost matrix, C. The problem calls for a selection of
one element in each row of the matrix so that all selected elements are in
different columns and the total sum of the selected elements is the smallest
possible.

Describe feasible solutions to the assignment problem as n- tuples <j1 , j2, ….,
jn> in which the ith component indicates the column n of the element
selected in the i th row. i.e.,

The job number assigned to the ith person. For eg <2,3,4,1> indicates a
feasible assignment of person 1 to job2, person 2 to job 3, person3 to job 4
and person 4 to job 1.

There is a one-to-one correspondence between feasible assignments and

permutations of the first n integers. If requires generating all the
permutations of integers 1,2,…n, computing the total cost of each assignment
by summing up the corresponding elements of the cost matrix, and finally
selecting the one with the smallest sum.

Based on number of permutations, the general case for this problem is n!,
which is impractical except for small instances. There is an efficient algorithm
for this problem called the Hungarian method.

This problem has a exponential problem solving algorithm, which is also an

efficient one. The problem grows exponentially, so there cannot be any
polynomial-time algorithm.
Divide and Conquer Strategy
Using the Divide and Conquer technique, we divide a problem into sub
problems. When the solution to each sub problem is ready, we 'combine' the
results from the sub problems to solve the main problem.

Suppose we had to sort an array A. A sub problem would be to sort a sub-

section of this array starting at index p and ending at index r, denoted
as A[p..r].

Divide
If q is the half-way point between p and r, then we can split the
subarray A[p..r] into two arrays A[p..q] and A[q+1, r].

Conquer
In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If
we haven't yet reached the base case, we again divide both these subarrays
and try to sort them.

Combine
When the conquer step reaches the base step and we get two sorted
subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the results by
creating a sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1,
r].
  Explain the method performing Multiplication of two large integers.
Explain how Divide conquer method can be used for the same. [Part
B MAY/JUNE 2016]

5. Multiplication of Large Integer

Large Integer Multiplication is a common procedure in computer-assisted

problem solving. Multiplying big numbers is not only difficult, but also time-
consuming and error-prone.

Look at two approaches to multiplying big numbers: the grade school method
and the divide and conquer method.

Large Integer Multiplication using Grade School Multiplication

In school, we studied the traditional multiplication technique. The multiplicand

is multiplied by each digit of the multiplier in that technique, and a partial
result of each multiplication is added by performing appropriate shifting. This
method is also known as the Traditional Multiplication Method.

The following example demonstrates how to perform grade school

multiplication in both American and English way.
This approach is simple to grasp, yet it is time-consuming and inefficient. If
multiplicand has n digits and multiplier has m digits, the complexity of
multiplication would be O(m n).

This technique takes quadratic time, which is insufficient for big numbers. Let’s
look into a more convenient method of multiplication.

Large Integer Multiplication using Divide and Conquer Approach

There are two ways to perform large integer multiplication using divide and
conquer. The first method – we call dumb method – does not improve the
running time. Second method – we call clever approach – performs better then
the traditional approach for integer multiplication.

Dumb Approach:

Let us represent number D as D = dn-1dn-2. . . d2d1d0. Each digit di is the ith least
significant digit in number D. Value of each position is given by,
d0 = 100 position
d1 = 101 position
d2 = 102 position
.
.
dn – 1 = 10n – 1 position.
According to position value,
45 = 4*101 + 5*100
23 = 2*101 + 3*100
For any real values a, b, c and d,
(a + b)*(c + d) = (a*c + a*d + b*c + b*d)
So, 45 * 23 = (4*101 + 5*100) * (2*101 + 3*100)
= (4 *2) *102 + (4*3 + 5*2) *101 + (5*3) *100
= 800 + 220 + 15
= 1035

Let’s derive formula to multiply two numbers of two digits each. Consider C = A
* B. If we consider A = a1a0 and B = b1b0, then
C = A * B = c2102 + c1101 + c0100
Where,
c2 = a1 * b1
c1 = a1* b0 + a0* b1
c0 = a0 * b0
This method does four multiplications, same as conventional method. This is as
dumb as grade school multiplication.
Example: Multiply 2345 with 678 using divide and conquer approach.

Solution:
Size of both operands must be even, so pad zero to the multiplier.
A = 2345 and B = 0678
A = a1a0 = 2345, hence a1 = 23 and a0 = 45
B = b1b0 = 0678, hence b1 = 06 and b0 = 78
C = A * B =c2104 + c1102 + c0100
c2 = a1 * b1
= 23 * 06
= 138

c1 = a1*b0 + a0*b1
= (23*78) + (45 * 06)
= 2064
c0 = a0 * b0
=(45 * 78)
= 3510
C = c2102 + c1101 + c0100
= 138*104 + 2064*102 + 3510
= 15, 89, 910

Clever Approach:

Previous DC approach does four multiplications. Let’s reformulate it to reduce

numbers of multiplications to three.

First approach:

According to dumb approach,

c2 = a1 * b1
c1 = a1*b0 + a0*b1 … (1)
c0 = a0*b0
Second approach:

Let us rewrite c1 as,

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)
= (a1b1 + a1b0 + a0b1 + a0b0) – (a1b1 + a0b0)
= a1*b0 + a0*b1 … (2)
Equation (1) and Equation (2) are the same, but the second approach of
computing c1 involves only one multiplication rather than two as it requires in
the first approach.

For A = a1a0 = 2345,

Hence, a1 = 23 and a0 = 45 and
B = b1b0 = 0678,
Hence, b1 = 06 and b0 = 78
c2 = a1 * b1
= 23 * 06
= 138
c0 = a0*b0
= (45 * 78)
= 3510

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

= (23 + 45) * (06 + 78) – (138 + 3510)
= 68 * 84 – 3648
= 2064

It is same as c1 = (a1*b0 + a0*b1) of dumb multiplication approach, but does only

one multiplication rather than two.
C = c2 * 104 + c1 * 102 + c0
= 1380000 + 206400 + 3510 = 15, 89, 910

This formulation leads to same result, with three multiplications only.

Generalization:

If size of integer is n digit, then we can generalize multiplication as,

C = c210n + c110n/2 + c0

Where, c2 = a1 * b1

c0 = a0*b0
c1 = (a1 + a0) * (b1 + b0) – c2 +c0)

This can be solved by applying recursion till n reaches to 1.

6. Strassen’s Matrix Multiplication

Strassen in 1969 gave an overview on how we can find the multiplication

of two 2*2 dimension matrices by the brute-force algorithm. But by
using the divide and conquer technique the overall complexity for the
multiplication of two matrices has been reduced. This happens by
decreasing the total number of multiplications performed at the expense
of a slight increase in the number of additions.

Strassen has used some formulas for multiplying the two 2*2 dimension
matrices where the number of multiplications is seven, additions and
subtractions are is eighteen, and in brute force algorithm, there is eight
number of multiplications and four addition.
 When the order n of matrix reaches infinity, the utility of Strassen’s
formula is shown by its asymptotic superiority. For example, let us
consider two matrices A and B of n*n dimension, where n is a power of
two. It can be observed that we can have four submatrices of order n/2 *
n/2 from A, B, and their product C where C is the resultant matrix
of A and B.

The procedure of Strassen’s matrix multiplication

Here is the procedure:

1. Divide a matrix of the order of 2*2 recursively until we get the matrix of order
2*2.
2. To carry out the multiplication of the 2*2 matrix, use the previous set of
formulas.
3. Subtraction is also performed within these eight multiplications and four
additions.
4. To find the final product or final matrix combine the result of two matrixes.
5.
Formulas for Strassen’s matrix multiplication.

Following are the formulae that are to be used for matrix multiplication.
1. D1 = (a11 + a22) * (b11 + b22)
2. D2 = (a21 + a22)*b11
3. D3 = (b12 – b22)*a11
4. D4 = (b21 – b11)*a22
5. D5 = (a11 + a12)*b22
6. D6 = (a21 – a11) * (b11 + b12)
7. D7 = (a12 – a22) * (b21 + b22)

C00= d1 + d4 – d5 + d7
C01 = d3 + d5
C10 = d2 + d4
C11 = d1 + d3 – d2 – d6
Here, C00, C01, C10, and C11 are the elements of the 2*2 matrix.
Algorithm for Strassen’s matrix multiplication

The algorithm for Strassen’s matrix Multiplication is as follows:

Algorithm Strass(n, x, y, z)

begin
If n = threshold then compute
C = x * y is a conventional matrix.
Else
Partition a into four sub matrices a00, a01, a10, a11.
Partition b into four sub matrices b00, b01, b10, b11.
Strass ( n/2, a00 + a11, b00 + b11, d1)
Strass ( n/2, a10 + a11, b00, d2)
Strass ( n/2, a00, b01 – b11, d3)
Strass ( n/2, a11, b10 – b00, d4)
Strass ( n/2, a00 + a01, b11, d5)
Strass (n/2, a10 – a00, b00 + b11, d6)
Strass (n/2, a01 – a11, b10 + b11, d7)

C = d1+d4-d5+d7 d3+d5
d2+d4 d1+d3-d2-d6

end if
return (C)
end.

Program for Strassen’s matrix multiplication

#include <stdio.h>
int main( )
{
int a[2][2],b[2][2],c[2][2],i,j;
int m1,m2,m3,m4,m5,m6,m7;
// Here we are scanning and printing the first matrix
printf("Enter the 4 elements of first matrix: ");
for(i=0;i<2;i++)
for(j=0;j<2;j++)
scanf("%d",&a[i][j]);
// Here we are scanning and printing the second matrix
printf("Enter the 4 elements of second matrix: ");
for(i=0;i<2;i++)
for(j=0;j<2;j++)
scanf("%d",&b[i][j]);

printf("\nThe first matrix is\n");

for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
printf("%d\t",a[i][j]);
}

printf("\nThe second matrix is\n");

for(i=0;i<2;i++){
printf("\n");
for(j=0;j<2;j++)
printf("%d\t",b[i][j]);
}
// Here we are applying the above mentioned formulae
m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]);
m2= (a[1][0]+a[1][1])*b[0][0];
m3= a[0][0]*(b[0][1]-b[1][1]);
m4= a[1][1]*(b[1][0]-b[0][0]);
m5= (a[0][0]+a[0][1])*b[1][1];
m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]);

c[0][0]=m1+m4-m5+m7;
c[0][1]=m3+m5;
c[1][0]=m2+m4;
c[1][1]=m1-m2+m3+m6;
// As we got the value of the elements, we now print them
printf("\n After performing multiplication \n");
for(i=0;i<2;i++){
printf("\n");
for(j=0;j<2;j++)
printf("%d\t",c[i][j]);
}

return 0;
}
This is all about Strassen’s matrix multiplication.
7. Closest Pair of Points using Divide and Conquer algorithm

An array of n points in the plane, and the problem is to find out the closest
pair of points in the array.
This problem arises in a number of applications.
For example, in air-traffic control, you may want to monitor planes that come
too close together, since this may indicate a possible collision.
Recall the following formula for distance between two points p and q.
The Brute force solution is O (n^2), compute the distance between each pair
and return the smallest.
Using Divide and Conquer strategy, Calculate the smallest distance in
O(n Log n) time and also O (n x (Log n)2) time.

Algorithm

Following are the detailed steps of a O(n x (Log n) 2) algorithm.

Input: An array of n points P [ ]

Output: The smallest distance between two points in the given array.

As a pre-processing step, the input array is sorted according to x coordinates.

1) Find the middle point in the sorted array; we can take P [n/2] as middle
point.

2) Divide the given array in two halves. The first subarray contains points
from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to
P[n-1].

3) Recursively find the smallest distances in both subarrays. Let the distances
be dl and dr. Find the minimum of dl and dr. Let the minimum be d.
4) From the above 3 steps, we have an upper bound d of minimum distance.
Now we need to consider the pairs such that one point in pair is from the left
half and the other is from the right half.

Consider the vertical line passing through P[n/2] and find all points whose x
coordinate is closer than d to the middle vertical line. Build an array strip [ ]
of all such points.

5) Sort the array strip [ ] according to y coordinates. This step is O(n Log n). It
can be optimized to O ( n) by recursively sorting and merging.

6) Find the smallest distance in strip [ ]. From the first look, it seems to be a
O(n2) step, but it is actually O(n). It can be proved geometrically that for every
point in the strip.

7) Finally return the minimum of d and distance calculated in the above step
(step 6)
Time Complexity of (n (log n)2)

Let Time complexity of above algorithm be T(n).

Let us assume that we use a O(n Log n) sorting algorithm.

The above algorithm divides all points in two sets and recursively calls for
two sets.

After dividing, it finds the strip in O(n) time, sorts the strip in O(n Log n) time
and finally finds the closest points in strip in O(n) time.

So T(n) can expressed as follows

T(n) = 2T(n/2) + O(n) + O(n Log n) + O(n)
T(n) = 2T(n/2) + O(n Log n)
T(n) = T(n x Log n x Log n)

Time Complexity of O (n Log n)

Let Time complexity of above algorithm be T(n).

Let us assume that we use a O(n Log n) sorting algorithm.

The above algorithm divides all points in two sets and recursively calls for
two sets.

After dividing, it finds the strip in O (n) time.

Also, it takes O(n) time to divide the Py array around the mid vertical line.

Finally finds the closest points in strip in O (n) time.

So T(n) can be expressed as follows

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

T(n) = 2T(n/2) + O(n)
T(n) = T(n Log n)
Example
[Link] hull Using Divide and Conquer Approach

Convex hull is the smallest region covering given set of points. Polygon is
called convex polygon if the angle between any of its two adjacent edges is
always less than 1800. Otherwise, it is called a concave polygon. Complex
polygons are self-intersecting polygons.

(a)Concave polygon (b) convex polygon (c) Complex polygon

The convex hull of the set of points Q is the convex polygon P that
encompasses all of the points given. The problem of finding the smallest
polygon P such that all the points of set Q are either on the boundary of P or
inside P is known as the convex hull problem. The convex hull of the points in
question is seen in following figure. The vertex of a polygon is a point shared
by two neighboring edges.

Convex hull of given points

Divide and Conquer Approach

There exist multiple approaches to solve convex hull problem. In this article,
we will discuss how to solve it using divide and conquer approach.

 Sort all of the points by their X coordinates. The tie is broken by ranking
points according to their Y coordinate.
 Determine two extreme points A and B, where A represents the leftmost
point and B represents the rightmost point. A and B would be the convex
hull’s vertices. Lines AB and BA should be added to the solution set.
 Find the point C that is the farthest away from line AB.
 Calculate the convex hull of the points on the line AC’s right and left
sides. Remove line AB from the original solution set and replace it with
AC and CB.
 Process the points on the right side of line BA in the same way.
 Find the convex hull of the points on the left and right of the line
connecting the two farthest points of that specific convex hull
recursively.

Algorithm of Convex Hull

Algorithm for finding convex hull using divide and conquer strategy is
provided below:

Algorithm for subroutine FindHull is described below :

Complexity analysis

Pre-processing step is to sort the points according to increasing order of their

X coordinate. Sorting can be done in O(nlog2n) time.

Finding two farthest points from the sorted list takes O(1) time.

Dividing points into two halves S1 and S2 take O(1) time by joining A and B.

In the average case, S1 and S2 contain half of the points. So, recursively
computing the convex hull of A and B takes T(n/2) each.

Merging of two convex hulls is done in linear time O(n), by finding the
orthogonally farthest point.

Total running time after preprocessing the points is given by,

T(n) = 2T(n/2) + O(n) + O(1)

= 2T(n/2) + n … (1)

Solving original recurrence for n/2,

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

Substituting this in equation (1),

T(n) = 2[ 2T(n/4) + n/2 ] + n

= 22 T(n/22) + 2n

After k substitutions,

T(n) = 2k T(n/2k) + k.n … (2)

Division of array creates binary tree, which has height log2n, so let us consider
that k grows up to log2n,

k = log2n ⇒ n = 2k

Substitute these values in equation (2)

T(n) = n.T(n/n) + log2n . n

T(n) = O(n.log2n)

Example of Convex Hull

Problem: Find the convex hull for a given set of points using divide and
conquer approach

Solution: Step 1: According to the algorithm, find left most and rightmost
points from the set P and label them as A and B. Label all the points on the right
of AB as S1 and all the points on the right of BA as S2.
Solution = {AB, BA}

Make a recursive call to FindHull (S1, A, B) and FindHull(S2 ,B, A)

Step 2 : Find Hull (S1 ,A, B)

Find point C orthogonally farthest from line AB

Solution = Solution – { AB } ∪ {AC, CB}

= {AC, CB, BA}

Label regions X0, X1 and X2 as shown in above figure

Make recursive calls: FindHull (X1, A, C) and FindHull (X2, C, B)

Step 3 : FindHull(X1, A, C)
Find point D orthogonally farthest from line AC

Solution = Solution – {AC} ∪ {AD, DC}

= {AD, DC, CB, BA}

Label regions X0, X1 and X2 as shown in above figure

Make recursive calls: FindHull (X1, A, D) and FindHull (X2, D, C)

But X1 and X2 sets are empty, so algorithm returns

Step 4 : FindHull(X2, C, B)

Find point E orthogonally farthest from line CB

Solution = Solution – {CB} ∪ {CE, EB}

= {AD, DC, CE, EB, BA}

Label regions X0, X1 and X2 as shown in Fig. P.3.6.1(d).

Make recursive calls: FindHull (X1, C, E) and FindHull (X2, E, B).

But X1 and X2 sets are empty, so algorithm returns Now we will explore the
points in S2, on the right-hand side of the line BA

Step 5 : FindHull(S2 ,B, A)

Find point F orthogonally farthest from line BA

Solution = Solution – {BA} ∪ {BF, FA}

= {AD, DC, CE, EB, BF, FA}

Label regions X0, X1 and X2 as shown in above figure.

Make recursive calls : FindHull (X1, B, F) and FindHull (X2, F, A)

But X1 set is empty, so call to FindHull (X1, B, F) returns

Step 6 : FindHull (X2, F, A)

Find point G orthogonally farthest from line FA

Solution = Solution – {FA} ∪ {FG, GA}

= {AD, DC, CE, EB, BF, FG, GA}

Label regions X0,

Collision avoidance: Because calculating collision-free routes is considerably

easier with a convex, it is frequently used to design paths.

The lowest area rectangle that encloses a polygon has at least one side flush
with the polygon’s convex hull, and hence the hull is computed in the first step
of minimum rectangle methods. Finding the smallest three-dimensional box
enclosing an item is also dependent on the 3D-convex hull.

X1 and X2 as shown in last figure

Make recursive calls: FindHull (X1, F, G) and FindHull (X2, G, A).

But X1 and X2 sets are empty, so algorithm returns. And no more recursive calls
are left. So polygon with edges (AD, DC, CE, EB, BF, FG, GA) is the convex hull of
given points.

Applications of Convex Hull

Collision avoidance: If the convex hull of car avoids collisions with

obstructions, so does the car. Because calculating collision-free routes is
considerably easier with a convex hull of vehicle, it is frequently used to design
paths.

Smallest Box: Convex hull helps to determine the minimum size required to
put object in in. It is useful to determine box size for the object. Finding the
smallest three-dimensional box enclosing an item is also dependent on the 3D-
convex hull.

Shape Analysis: Convex hull of object is useful to analyze the shape of object.

Pattern recognition, image processing, statistics, geographic information

systems, game theory, phase diagram creation, and static code analysis via
abstract interpretation are some more practical scenarios where convex hull
plays important role.

It is also a building component for a variety of other computational-geometric

methods, such as the rotating calipers technique for calculating the breadth
and diameter of given set of points.
 8. DECREASE AND CONQUER

As divide-and-conquer approach is already discussed, which include

following steps:

Divide the problem into a number of subproblems that are smaller

instances of the same problem.
Conquer the sub problems by solving them recursively. If the sub
problem sizes are small enough, however, just solve the sub problems in a
straightforward manner.
Combine the solutions to the sub problems into the solution for the
original problem. Similarly, the approach decrease-and-conquer works, it
also include following steps:

Decrease or reduce problem instance to smaller instance of the same

problem and extend solution.
Conquer the problem by solving smaller instance of the problem.
Extend solution of smaller instance to obtain solution to original problem.
Basic idea of the decrease-and-conquer technique is based on exploiting
the relationship between a solution to a given instance of a problem and a
solution to its smaller instance. This approach is also known as
incremental or inductive approach.

The decrease-and-conquer technique is based on exploiting the

relationship between a solution to a given instance of a problem and a
solution to its smaller instance. Once such a relationship is established, it
can be exploited either top down or bottom up. The former leads naturally
to a recursive implementation, although, as one can see from several
examples in this chapter, an ultimate implementation may well be non-
recursive.

The bottom-up variation is usually implemented iteratively, starting with a

solution to the smallest instance of the problem; it is called sometimes
the incremental approach. There are three major variations of decrease-
and-conquer: decrease by a constant decrease by a constant factor variable
size decrease
In the decrease-by-a-constant variation, the size of an instance is reduced
by the same constant on each iteration of the algorithm. Typically, this
constant is equal to one (Figure 1), although other constant size reductions
do happen occasionally.

Consider, as an example, the exponentiation problem of

computing an where a = 0 and n is a nonnegative integer. The relationship
between a solution to an instance of size n and an instance of size n − 1 is
obtained by the obvious formula an = an−1 . a. So the function f (n) = an can
be computed either “top down” by using its recursive definition

or “bottom up” by multiplying 1 by a n times. (Yes, it is the same as the

brute-force algorithm, but we have come to it by a different thought
process.) More interesting examples of decrease-by-one algorithms

The decrease-by-a-constant-factor technique suggests reducing a problem

instance by the same constant factor on each iteration of the algorithm. In
most applications, this constant factor is equal to two. (Can you give an
example of such an algorithm?) The decrease-by-half idea is illustrated in
Figure 2.
For an example, let us revisit the exponentiation problem. If the instance of
size n is to compute an, the instance of half its size is to compute an/2, with
the obvious relationship between the two: an = (an/2)2. But since we
consider here instances with integer exponents only, the former does not
work for odd n. If n is odd, we have to compute an−1 by using the rule for
even-valued exponents and then multiply the result by a. To summarize, we
have the following formula:

If we compute an recursively according to formula and measure the algo-

rithm’s efficiency by the number of multiplications, we should expect the
algorithm to be in (log n) because, on each iteration, the size is reduced by
about a half at the expense of one or two multiplications.

A few other examples of decrease-by-a-constant-factor algorithms are

given in Section 4.4 and its exercises. Such algorithms are so efficient,
however, that there are few examples of this kind.
 Finally, in the variable-size-decrease variety of decrease-and-conquer, the
size-reduction pattern varies from one iteration of an algorithm to another.
Eu-clid’s algorithm for computing the greatest common divisor provides a
good ex-ample of such a situation. Recall that this algorithm is based on the
formula

gcd(m, n) = gcd(n, m mod n).

Though the value of the second argument is always smaller on the right-
hand side than on the left-hand side, it decreases neither by a constant nor
by a constant factor. A few other examples of such algorithms appear in
Section

Topological Sort-
Topological Sort is a linear ordering of the vertices in such a way that if
there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’, then ‘u’ comes
before ‘v’ in the ordering.
It is important to note that-
 Topological Sorting is possible if and only if the graph is a Directed
Acyclic Graph.
 There may exist multiple different topological orderings for a given
directed acyclic graph.

Topological Sort Example-

Consider the following directed acyclic graph-

 For this graph, following 4 different topological orderings are possible-
 123456
 123465
 132456
 132465
Applications of Topological Sort-

Few important applications of topological sort are-

 Scheduling jobs from the given dependencies among jobs
 Instruction Scheduling
 Determining the order of compilation tasks to perform in makefiles
 Data Serialization

Problem-01:

Find the number of different topological orderings possible for the given
graph-

Solution-
 The topological orderings of the above graph are found in the following
steps-

Step-01:

Write in-degree of each vertex-

Step-02:

 Vertex-A has the least in-degree.

 So, remove vertex-A and its associated edges.
 Now, update the in-degree of other vertices.
 Step-03:

 Vertex-B has the least in-degree.

 So, remove vertex-B and its associated edges.
 Now, update the in-degree of other vertices.

Step-04:
There are two vertices with the least in-degree. So, following 2 cases are
possible-
In case-01,
 Remove vertex-C and its associated edges.
 Then, update the in-degree of other vertices.
In case-02,
 Remove vertex-D and its associated edges.
 Then, update the in-degree of other vertices.
 Step-05:

Now, the above two cases are continued separately in the similar manner.

In case-01,
 Remove vertex-D since it has the least in-degree.
 Then, remove the remaining vertex-E.

In case-02,
 Remove vertex-C since it has the least in-degree.
 Then, remove the remaining vertex-E.

Conclusion-

For the given graph, following 2 different topological orderings are

possible-
 ABCDE
 ABDCE

Problem-02:

Find the number of different topological orderings possible for the given
graph-
 Solution-

The topological orderings of the above graph are found in the following
steps-
Step-01:
Write in-degree of each vertex-

Step-02:
Vertex-1 has the least in-degree.
 So, remove vertex-1 and its associated edges.
 Now, update the in-degree of other vertices.
 Step-03:
There are two vertices with the least in-degree. So, following 2 cases are
possible-
In case-01,
 Remove vertex-2 and its associated edges.
 Then, update the in-degree of other vertices.

In case-02,
 Remove vertex-3 and its associated edges.
 Then, update the in-degree of other vertices.

Step-04:
Now, the above two cases are continued separately in the similar manner.
In case-01,
 Remove vertex-3 since it has the least in-degree.
 Then, update the in-degree of other vertices.

In case-02,
 Remove vertex-2 since it has the least in-degree.
 Then, update the in-degree of other vertices.
 Step-05:

In case-01,
 Remove vertex-4 since it has the least in-degree.
 Then, update the in-degree of other vertices.

In case-02,
 Remove vertex-4 since it has the least in-degree.
 Then, update the in-degree of other vertices.
 Step-06:

In case-01,
 There are 2 vertices with the least in-degree.
 So, 2 cases are possible.
 Any of the two vertices may be taken first.

Same is with case-02.

Conclusion-

For the given graph, following 4 different topological orderings are

possible-
 123456
 123465
 132456
 132465
9. TRANSFORM AND CONQUER

[Link]

Transform and Conquer: Instances and Structuring

Either the problem or algorithm can be transformed in one of three
ways:
Instance simplification: the instances of the problem can be
transformed into an easier instance to solve.
Representation change: the data structure can be
transformed so that it is more efficient.
Problem reduction: the problem can be transformed to an easier
problem to solve.

Problem’s simpler instance

instance or
solution another
representation
or
another problem’s instance

This lecture gives examples of instance simplification and

representation change.

Presorting: Instance simplification

"Presorting" is a common example of "instance simplification."
Presorting is sorting ahead of time, to make repetitive solutions
faster.
For example if you wish to find many kth statistics in an array
then it might make sense to sort the array ahead of time for so
that the cost for determining each statistics is constant time.
Presorting is a form of preconditioning. Preconditioning is
manipulating the data to make the algorithm faster.

Example 1: Determine the uniqueness of array elements.

The brute force algorithm would compare each array element
with the rest of the array.
Alternatively, we can sort the array first and then check only its
consecutive elements: if the array has equal elements, a pair of
 them must be next to each other, and vice versa.
The cost for determining uniqueness (without the sorting cost) is
Θ(n).
ALGORITHM PresortElementUniqueness(A[0..n − 1])
//Solves the element uniqueness problem by sorting the array first
//Input: An array A[0..n − 1] of orderable elements
//Output: Returns “true” if A has no equal elements, “false” otherwise
sort the array A

for i ← 0 to n − 2 do
if A[i] = A[i + 1]
return false
return true

The running time of this algorithm is the sum of the time spent
on sorting and the time spent on checking consecutive
elements.
Since the former requires at least n log n comparisons and the
latter needs no more than n − 1 comparisons, it is the sorting
part that will determine the overall efficiency of the algorithm.
So, if we use a quadratic sorting algorithm here, the entire
algorithm will not be more
efficient than the brute-force one.
But if we use a good sorting algorithm, such as mergesort, with
worst-case efficiency in ѳ(n log n), the worst-case efficiency of
the entire presorting-based algorithm will be also in ѳ(n log n):
The total cost is
T(n) = Tsort(n) + Tscan(n) ε Θ(n log n) + Θ(n) = Θ(n log n)

EXAMPLE 2 : Computing a mode

A mode is a value that occurs most often in a given list of
numbers. For example, for 5, 1, 5, 7, 6, 5, 7, the mode is 5. (If
several different values occur most often, any of them can be
considered a mode.)
The brute-force approach to computing a mode would scan the
list and compute the frequencies of all its distinct values, then
find the value with the largest frequency.
In order to implement this idea, we can store the values already
encountered, along with their frequencies, in a separate list.
On each iteration, the ith element of the original list is
compared with the values already encountered by traversing
this auxiliary list.
If a matching value is found, its frequency is incremented;
otherwise, the current element is added to the list of distinct
values seen so far with a frequency of 1.
The worst-case input for this algorithm is a list with no equal
elements. For such a list, its ith element is compared with i − 1
elements of the auxiliary list of distinct values seen so far before
being added to the list with a frequency of 1.
As a result, the worst-case number of comparisons made by this
algorithm in creating
the frequency list is

The additional n − 1 comparisons needed to find the largest

frequency in the aux-iliary list do not change the quadratic worst-
case efficiency class of the algorithm.
As an alternative, let us first sort the input. Then all equal values
will be adjacent to each other. To compute the mode, all we need
to do is to find the longest run of adjacent equal values in the
sorted array.

ALGORITHM PresortMode(A[0..n − 1])

//Computes the mode of an array by sorting it first

//Input: An array A[0..n − 1] of orderable elements
//Output: The array’s mode
sort the
array A i ←
0
modefrequency ← 0
while i ≤ n − 1 do
runlengt h ← 1; runvalue ← A[i]
while i + runlength ≤ n − 1 and A[i +
runlength] = runvalue runlengt h ←
runlengt h + 1
 if runlength > modefrequency
modefrequency ← runlength;
modevalue ← runvalue i ← i + runlength
return modevalue

The analysis here is similar to the analysis of Example 1: the

running time of the algorithm will be dominated by the time
spent on sorting since the remainder of the algorithm takes
linear time.
Consequently, with an n log n sort, this method’s worst-case
efficiency will be in a better asymptotic class than the worst-case
efficiency of the brute-force algorithm.
EXAMPLE 3 : Searching problem
 Consider the problem of searching for a given value v in a
given array of n sortable items. The brute-force solution
here is sequential search , which needs n comparisons
in the worst case.
 If the array is sorted first, we can then apply binary search,
which requires only
log2 n + 1 comparisons in the worst case.
 Assuming the most efficient n log n sort, the total running time
of such a searching algorithm in the worst case will be

 which is inferior to sequential search. The algorithm runs

in linear time, so thecost of sorting is presorting the array.
 Geometrical problems frequently sort the collection of
points before solving the problem. Also diagraphs
algorithms frequently do a topological sort before running.

 Explain Heap sort method [ Part B- NOV/DEC 2020]

 Explain min heap and max heap operation with an example [
Part B- APR/MAY 2020]
9.2. Heaps and Heapsort
A heap is a priority queue that is a complete tree. A priority queue
is a multiset of items
with an orderable characteristic called an item’s priority, with the
following operations:
finding an item with the highest (i.e., largest) priority
deleting an item with the highest priority
adding a new item to the multiset

Notion of the Heap

DEFINITION: A heap can be defined as a binary tree with keys
assigned to its nodes, one key per node, provided the following two
conditions are met:
The shape property—the binary tree is essentially complete
(or simply com-plete), i.e., all its levels are full except possibly
the last level, where only some rightmost leaves may be missing.
parental dominance or heap property—the key in each node is
greater than or equal to the keys in its children. (This condition is
considered auto-matically satisfied for all leaves.)
For example, consider the trees of Figure 6.9.

 The first tree is a heap. The second one is not a heap, because the
tree’s shape property is violated. And the third one is not a heap,
because the parental dominance fails for the node with key 5.
 Note that key values in a heap are ordered top down; i.e., a sequence of
values on any path
from the root to a leaf is decreasing (nonincreasing, if equal keys are
allowed).
 There is no left-to-right order in key values; i.e., there is no relationship
among key values for nodes either on the same level of the tree or, in

the left and right subtrees of the same node.

Properties of Heaps
1. The height of a heap is floor(lg n).
2. The root contains the highest priority item.
3. A node and all the descendants is a heap
4. A heap can be implemented using an array and all operations are
in-place.
5. if index of the root = 1 then index of left child = 2i and right child =
2i+1
6. Level i of the heap has 2i elements
7. heap order, the parent value is larger than the children
Thus, we could also define a heap as an array H [1..n] in which every
element in position i in the first half of the array is greater than or
equal to the elements in positions 2i and 2i + 1, i.e.,H [i] ≥ max{H [2i],
H [2i + 1]} for i = 1, . . . , n/2 .

To construct a heap, there are two principal alternatives.

The first is the bottom-up heap construction algorithm illustrated in
Figure 6.11.
It initializes the essentially complete binary tree with n nodes by
placing keys in the order given and then “heapifies” the tree as
follows. Starting with the last parental node, the algorithm
checks whether the parental dominance holds for the key in this
node.
 If it does not, the algorithm exchanges the node’s key K with the
larger key of its children and checks whether the parental
dominance holds for K in its new position.
This process continues until the parental dominance for K is
satisfied.
After completing the “heapification” of the subtree rooted at the
current parental node, the algorithm proceeds to do the same
for the node’s immediate predecessor. The algorithm stops after
this is done for the root of the tree.
ALGORITHM HeapBottomUp(H [1..n])

//Constructs a heap from elements of a given array by the bottom-up

algorithm
//Input: An array H [1..n] of orderable items
//Output: A heap H [1..n]
for i ←<n/2> downto 1 do
k ← i; v ← H [k]
heap ← false
while not heap and 2 ∗ k ≤ n do
j←2∗k
if j < n //there are two children
if H [j ] < H [j + 1] j ← j + 1
if v ≥ H [j ]
heap ← true
else H [k] ← H
[j ]; k ← j H [k]
←v

Assume that n = 2k − 1 so that a heap’s tree is full, i.e., the largest

possible number of
nodes occurs on each level.
 Let h be the height of the tree according to the first property of
heaps , h = log2 n or just log2 (n + 1) − 1 = k − 1 for the specific
values of n.
Each key on level i of the tree will travel to the leaf level h in the
worst case of the heap construction algorithm.
Since moving to the next level down requires two comparisons—
one to find the larger child and the other to determine whether
the exchange is required—the total number of key comparisons
involving a key on level i will be 2(h − i).
Therefore, the total number of key comparisons in the worst case

will be
The second is top-down heap construction algorithm
It constructs a heap by successive insertions of a new key into a
previously constructed heap.
To insert a new key K into a heap, First attach a new node with
key K in it after the last leaf of the existing heap. Then sift K up
to its appropriate place in the new heap as follows.
Compare K with its parent’s key: if the latter is greater than or
equal to K, stop (the
structure is a heap); otherwise, swap these two keys and
compare K with its new parent.
This swapping continues until K is not greater than its last
parent or it reaches the root (illustrated in Figure 6.12).
This insertion operation cannot require more key comparisons
than the heap’s height.
Since the height of a heap with n nodes is about log2 n, the time
efficiency of insertion is in O(log n).
Maximum Key Deletion from a heap
Step 1 Exchange the root’s key with the last key K of the heap.
Step 2 Decrease the heap’s size by 1.
Step 3 “Heapify” the smaller tree by sifting K down the tree exactly in
the same way we did it in the bottom-up heap construction algorithm.
That is, verify the parental dominance for K: if it holds, we are done; if
not, swap K with the larger of its children and repeat this operation
until the parental dominance condition holds for K in its new position.
The efficiency of deletion is determined by the number of key
comparisons needed to “heapify” the tree after the swap has been
made and the size of the tree is decreased by 1. Since this cannot
require more key comparisons than twice the heap’s height, the time
efficiency of deletion is in O(log n) as well.

Heapsort
An interesting sorting algorithm discovered by J. W. J. Williams .
This is a two-stagealgorithm that works as follows.
Stage 1 (heap construction): Construct a heap for a given array.
Stage 2 (maximum deletions): Apply the root-deletion operation n − 1
times to the remaining heap.
As a result, the array elements are eliminated in decreasing
order.
But since under the array implementation of heaps an element
being deleted is placed last, the resulting array will be exactly
the original array sorted in increasing order.

Heapsort is traced on a specific input in Figure

The heap construction of the algorithm is in O(n), we have to

investigate just the time efficiency of the second stage.
For the number of key comparisons, C(n), needed for
eliminating the root keys from the heaps of diminishing sizes
from n to 2, we get the following inequality:
 This means that C(n) ∈ O(n log n) for the second stage of heapsort.
For both stages, we get O(n) + O(n log n) = O(n log n).
The time efficiency of heapsort is (n log n) in both the worst and
average cases.

Heap Sort Algorithm

Heap sort processes the elements by creating the min-heap or max-heap
using the elements of the given array. Min-heap or max-heap represents
the ordering of array in which the root element represents the minimum or
maximum element of the array.

Heap sort basically recursively performs two main operations -

o Build a heap H, using the elements of array.

o Repeatedly delete the root element of the heap formed in 1st phase.

What is a heap?

A heap is a complete binary tree, and the binary tree is a tree in which the
node can have the utmost two children. A complete binary tree is a binary
tree in which all the levels except the last level, i.e., leaf node, should be
completely filled, and all the nodes should be left-justified.

What is heap sort?

Heapsort is a popular and efficient sorting algorithm. The concept of heap

sort is to eliminate the elements one by one from the heap part of the list,
and then insert them into the sorted part of the list.

Heapsort is the in-place sorting algorithm. Now, let's see the algorithm of
heap sort.

Algorithm
1. HeapSort(arr)
2. BuildMaxHeap(arr)
3. for i = length(arr) to 2
4. swap arr[1] with arr[i]
5. heap_size[arr] = heap_size[arr] ? 1
6. MaxHeapify(arr,1)
7. End

BuildMaxHeap(arr)

BuildMaxHeap(arr)
1. heap_size(arr) = length(arr)
2. for i = length(arr)/2 to 1
3. MaxHeapify(arr,i)
4. End

MaxHeapify(arr,i)

1. MaxHeapify(arr,i)
2. L = left(i)
3. R = right(i)
4. if L ? heap_size[arr] and arr[L] > arr[i]
5. largest = L
6. else
7. largest = i
8. if R ? heap_size[arr] and arr[R] > arr[largest]
9. largest = R
10. if largest != i
11. swap arr[i] with arr[largest]
12. MaxHeapify(arr,largest)
13. End

Working of Heap sort Algorithm

In heap sort, basically, there are two phases involved in the sorting of
elements. By using the heap sort algorithm, they are as follows -

o The first step includes the creation of a heap by adjusting the

elements of the array.
 o After the creation of heap, now remove the root element of the heap
repeatedly by shifting it to the end of the array, and then store the
heap structure with the remaining elements.

Now let's see the working of heap sort in detail by using an example. To
understand it more clearly, let's take an unsorted array and try to sort it
using heap sort. It will make the explanation clearer and easier.

First, we have to construct a heap from the given array and convert it into
max heap.

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete
this node, we have to swap it with the last node, i.e. (11). After deleting the
root element, we again have to heapify it to convert it into max heap.
After swapping the array element 89 with 11, and converting the heap into
max-heap, the elements of array are -

In the next step, again, we have to delete the root element (81) from the
max heap. To delete this node, we have to swap it with the last node,
i.e. (54). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into
max-heap, the elements of array are -

In the next step, we have to delete the root element (76) from the max heap
again. To delete this node, we have to swap it with the last node,
i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into
max-heap, the elements of array are -
In the next step, again we have to delete the root element (54) from the
max heap. To delete this node, we have to swap it with the last node,
i.e. (14). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (22) from the
max heap. To delete this node, we have to swap it with the last node,
i.e. (11). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (14) from the
max heap. To delete this node, we have to swap it with the last node,
i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (11) from the
max heap. To delete this node, we have to swap it with the last node,
i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are -

Now, the array is completely sorted.

Implementation of Heapsort
 Program: Write a program to implement heap sort in C language.

1. #include <stdio.h>
2. /* function to heapify a subtree. Here 'i' is the
3. index of root node in array a[], and 'n' is the size of heap. */
4. void heapify(int a[], int n, int i)
5. {
6. int largest = i; // Initialize largest as root
7. int left = 2 * i + 1; // left child
8. int right = 2 * i + 2; // right child
9. // If left child is larger than root
10. if (left < n && a[left] > a[largest])
11. largest = left;
12. // If right child is larger than root
13. if (right < n && a[right] > a[largest])
14. largest = right;
15. // If root is not largest
16. if (largest != i) {
17. // swap a[i] with a[largest]
18. int temp = a[i];
19. a[i] = a[largest];
20. a[largest] = temp;
21.
22. heapify(a, n, largest);
23. }
24. }
25. /*Function to implement the heap sort*/
26. void heapSort(int a[], int n)
27. {
28. for (int i = n / 2 - 1; i >= 0; i--)
29. heapify(a, n, i);
30. // One by one extract an element from heap
31. for (int i = n - 1; i >= 0; i--) {
32. /* Move current root element to end*/
33. // swap a[0] with a[i]
34. int temp = a[0];
35. a[0] = a[i];
36. a[i] = temp;
37. heapify(a, i, 0);
38. }
39. }
40. /* function to print the array elements */
41. void printArr(int arr[], int n)
42. {
43. for (int i = 0; i < n; ++i)
44. {
45. printf("%d", arr[i]);
46. printf(" ");
47. }
48. }
49. int main()
50. {
51. int a[] = {48, 10, 23, 43, 28, 26, 1};
52. int n = sizeof(a) / sizeof(a[0]);
53. printf("Before sorting array elements are - \n");
54. printArr(a, n);
55. heapSort(a, n);
56. printf("\nAfter sorting array elements are - \n");
57. printArr(a, n);
58. return 0;
59. }

Output

Advantages of using Heap Sort in Data Structure

 Optimized performance, efficiency, and accuracy are a few of the best

qualities of this algorithm.
 The algorithm is also highly consistent with very low memory usage. No
extra memory space is required to work, unlike the Merge Sort or
recursive Quick Sort.
 Simple
 Non recursive
 Low auxiliary storage requirement
 Consistently high performance: its best and worst cases are within a
tiny constant factor of each other, as well as the theoretical lower
bound for comparison sorts.

Disadvantages of using Heap Sort in Data Structure

 Heap Sort is considered unstable, expensive, and not very efficient

when working with highly complex data.
 Poor locality of reference
 Inherently serial in nature
Divide and Conquer Strategy
Using the Divide and Conquer technique, we divide a problem into sub
problems. When the solution to each sub problem is ready, we 'combine' the
results from the sub problems to solve the main problem.

Suppose we had to sort an array A. A sub problem would be to sort a sub-

section of this array starting at index p and ending at index r, denoted
as A[p..r].

Divide
If q is the half-way point between p and r, then we can split the
subarray A[p..r] into two arrays A[p..q] and A[q+1, r].

Conquer
In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If
we haven't yet reached the base case, we again divide both these subarrays
and try to sort them.

Combine
When the conquer step reaches the base step and we get two sorted
subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the results by
creating a sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1,
r].
Binary Search

What is Search?
Search is a process of finding a value in a list of values. In other words,
searching is the process of locating given value position in a list of values.

Why is binary search important?

Binary search is an efficient algorithm for finding an item from a sorted list of
items. It works by repeatedly dividing in half the portion of the list that could
contain the item, until you’ve narrowed down the possible locations to just one.

Binary Search Algorithm

 The binary search algorithm can be used with only a sorted list of elements.
That means the binary search is used only with a list of elements that are
already arranged in an order.

 The binary search cannot be used for a list of elements arranged in random
order.

 This search process starts comparing the search element with the middle
element in the list. If both are matched, then the result is "element found".

 Otherwise, we check whether the search element is smaller or larger than

the middle element in the list.

 If the search element is smaller, then we repeat the same process for the
left sublist of the middle element.

 If the search element is larger, then we repeat the same process for the
right sublist of the middle element.

 We repeat this process until we find the search element in the list or until
we left with a sublist of only one element. And if that element also doesn't
match with the search element, then the result is "Element not found in the
list".
 Binary search algorithm finds a given element in a list of elements
with O(log n) time complexity where n is total number of elements in the
list.

Binary search is implemented using following steps.

Step 1 - Read the search element from the user.

Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted
list.
Step 4 - If both are matched, then display "Given element is found!!!" and
terminate the function.
Step 5 - If both are not matched, then check whether the search element is
smaller or larger than the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2,
3, 4 and 5 for the left sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3,
4 and 5 for the right sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or
until sublist contains only one element.
Step 9 - If that element also doesn't match with the search element, then
display "Element is not found in the list!!!" and terminate the function.

Example 1

Consider the following list of elements and the element to be searched...

Example 2

To understand the working of the Binary search algorithm, let's take a sorted
array. It will be easy to understand the working of Binary search with an
example.

There are two methods to implement the binary search algorithm -

o Iterative method
o Recursive method

The recursive methods of binary search follow the divide and conquer
approach.

Let the elements of array are -

 Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

1. mid = (beg + end)/2

So, in the given array -

beg = 0

end = 8

mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

Now, the element to search is found. So algorithm will return the index of the
element matched.
Implementation of Binary Search Algorithm using C Programming Language

#include<stdio.h>
#include<conio.h>
void main()
{
int first, last, middle, size, i, s Element, list[100];
clrscr ( );
printf("Enter the size of the list: ");
scanf("%d",&size);
printf("Enter %d integer values in Ascending order\n", size);
for (i = 0; i < size; i++)
scanf("%d",&list[i]);
printf("Enter value to be search: ");
scanf("%d", &sElement);
first = 0;
last = size - 1;
middle = (first+last)/2;
while (first <= last) {
if (list[middle] < sElement)
first = middle + 1;
else if (list[middle] == sElement)
{
printf("Element found at index %d.\n",middle);
break;
}
else
last = middle - 1;
 middle = (first + last)/2;
}
if (first > last)
printf("Element Not found in the list.");
getch();
}
Complexity Analysis of Binary Search

Best Case:

In binary search, the key is initially compared to the array’s middle element. If
the key is in the center of the array, the algorithm only does one comparison,
regardless of the size of the array. As a result, the algorithm’s best-case
running time is T(n) = 1.

Worst Case:

Every iteration the binary search, search space is decreased by half, allowing
for maximum log2n array divisions. If the key is at the leaf of the tree or it is
not present at all, then the algorithm does log2n comparisons, which is
maximum. The number of comparisons increases in logarithmic proportion
to the amount of the input. As a result, the algorithm’s worst-case running
time would be T(n) = O(log2 n).

The problem size is reduced by a factor of two after each iteration, and the
method does one comparison.

Recurrence of binary search can be written as T(n) = T(n/2) + 1.

Solution to this recurrence leads to same running time, i.e. O(log2n). Detail
derivation is discussed here:

In every iteration, the binary search does one comparison and creates a new
problem of size n/2. So recurrence equation of binary search is given as,

T(n) = T(n/2) + 1, if n > 1

T(n) = 1, if n = 1
Only one comparison is needed when there is only one element in the array.
That’s the trivial case. This is the boundary condition for recurrence. Let us
solve this by iterative approach,

T (n) = T(n/2) + 1 …(1)

Substitute n by n/2 in Equation (1) to find T(n/2)

T(n/2) = T(n/4) + 1 …(2)

Substitute value of T(n/2) in Equation (1),

T(n) = T(n/22) + 1 …(3)

Substitute n by n/2 in Equation (2) to find T(n/4),

T(n/4) = T(n/8) + 1

Substitute value of T(n/4) in Equation (3),

T(n) = T(n/23) + 3

After k iterations,

T(n) = T(nk) + k

Binary tree created by binary search can have maximum height log2n

So, k = log2n ⇒ n = 2k

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

= T(1) + k

From base case of recurrence,

T(n) = 1 + k = 1 + log2n

T(n) = O(log2n)
 Average Case:

The average case for binary search occurs when the key element is neither in
the middle nor at the leaf level of the search tree. On average, it does half of
the log2 n comparisons, which will turn out as T (n) = O(log2 n).

The complexity of linear search and binary search for all three cases is
compared in the following table.

Best case Average case Worst case

Binary Search O(1) O(log2n) O(log2n)

Linear Search O(1) O(n) O(n)

Linear Search vs. Binary Search

Linear Search Binary Search

Efficient but not as simple as a

Simple but not efficient.
linear search.

Works on the random list also The list must be sorted.

In the worst case, only log2n

In the worst case, all elements
elements are compared with the
are compared with the key.
key.

In the best case, the element is In the best case, the element is in
in the first position of the array. the middle of the array.

Average case = Worst case = Average case = Worst case =

O(n) O(log2n)

Binary Search Algorithm Advantages-

The advantages of binary search algorithm are-

 It eliminates half of the list from further searching by using the result of
each comparison.
  It indicates whether the element being searched is before or after the
current position in the list.
 This information is used to narrow the search.
 For large lists of data, it works significantly better than linear search.

Binary Search Algorithm Disadvantages-

The disadvantages of binary search algorithm are-
 It employs recursive approach which requires more stack space.
 Programming binary search algorithm is error prone and difficult.
 The interaction of binary search with memory hierarchy i.e. caching is poor.
(because of its random access nature)

Merge Sort Algorithm

 Merge sort is the sorting technique that follows the divide and conquers
approach. Merge sort is similar to the quick sort algorithm as it uses the
divide and conquers approach to sort the elements.
 It is one of the most popular and efficient sorting algorithm. It divides
the given list into two equal halves, calls itself for the two halves and
then merges the two sorted halves.

We have to define the merge ( ) function to perform the merging.

 The sub-lists are divided again and again into halves until the list cannot
be divided further.
 Then we combine the pair of one element lists into two-element lists,
sorting them in the process.
 The sorted two-element pairs are merged into the four-element lists,
and so on until we get the sorted list.

Algorithm
In the following algorithm, arr is the given array, beg is the starting element,
and end is the last element of the array.

1. MERGE_SORT(arr, beg, end)

2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
10. END MERGE_SORT

The important part of the merge sort is the MERGE function. This function
performs the merging of two sorted sub-arrays that
are A[beg…mid] and A[mid+1…end], to build one sorted array A[beg…end].
So, the inputs of the MERGE function are A[ ], beg, mid, and end.

The implementation of the MERGE function is given as follows -

/* Function to merge the subarrays of a[ ] */

1. void merge(int a[], int beg, int mid, int end)
2. {
3. int i, j, k;
4. int n1 = mid - beg + 1;
5. int n2 = end - mid;
6. int LeftArray[n1], RightArray[n2]; //temporary arrays
7. /* copy data to temp arrays */
8. for (int i = 0; i < n1; i++)
9. LeftArray[i] = a[beg + i];
10. for (int j = 0; j < n2; j++)
11. RightArray[j] = a[mid + 1 + j];
12. i = 0, /* initial index of first sub-array */
13. j = 0; /* initial index of second sub-array */
14. k = beg; /* initial index of merged sub-array */
15. while (i < n1 && j < n2)
16. {
17. if(LeftArray[i] <= RightArray[j])
18. {
19. a[k] = LeftArray[i];
20. i++;
21. }
22. else
23. {
24. a[k] = RightArray[j];
25. j++;
26. }
27. k++;
 28. }
29. while (i<n1)
30. {
31. a[k] = LeftArray[i];
32. i++;
33. k++;
34. }
35. while (j<n2)
36. {
37. a[k] = RightArray[j];
38. j++;
39. k++;
40. }
41. }

Working of Merge sort Algorithm

To understand the working of the merge sort algorithm, let's take an unsorted
array. It will be easier to understand the merge sort via an example1.

Let the elements of array are -

According to the merge sort, first divide the given array into two equal halves.
Merge sort keeps dividing the list into equal parts until it cannot be further
divided.

As there are eight elements in the given array, so it is divided into two arrays
of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide
them into new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further
divided.
Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them
into another array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25
and 8, and in the list of two values, put 8 first followed by 25.

Then compare 32 and 17, sort them and put 17 first followed by 32. After that,
compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data
values and merge them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above
arrays, the array will look like -

Now, the array is completely sorted.

Example 2

Complexity Analysis

 On each recursive call, the list is divided into two sublists, and problem
size reduces by half. After sorting two sublists of size (n / 2), combine
procedure takes n comparisons to form the sorted list of size n.

 Total running time of merge sort is computed by summing complexity of

following three steps:
  Divide: This step computes the middle index of the array, which can be
done in constant time. Thus, D(n) = Q(1).
 Conquer: We recursively solve two sub problems, each of size (n / 2),
which contributes 2T(n/2) to the running time.
 Combine: COMBINE procedure merges two sub lists, each of size n/2
and does n comparisons, thus C(n) = Q(n).
 Hence, T(n) = T(Conquer) + T(Divide) + T(Combine)

T(n) = 0, if n = 1

T(n) = T(n/2) + T(n/2) + D(n) + C(n), if n > 1

The first T(n/2) = Cost for solving left sub list

The second T(n/2) = Cost for solving right sub list

D(n) is cost of division, which is constant, i.e. O(1) as the list splitting is
done simply by computing the middle of the array

C(n) is cost of conquer, which is linear, i.e. O(n) as two sub lists each of size
n/2 are merged into bigger sorted array of size n with the help of
maximum n comparisons

So, T(n) = 2T(n/2) + O(1) + O(n)

T(n) = 2T(n/2) + n … (1)

Derive the time complexity of merge sort using two methods:

 Substitution method
 Master method

Substitution method:

Solving original recurrence for n/2,

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

Substituting this in equation (1),

T(n) = 2[ 2T(n/4) + n/2 ] + n

= 22 T(n/22) + 2n
.

After k substitutions,

T(n) = 2k T(n/2k) + k.n … (2)

Division of array creates binary tree, which has height log2n, so let us consider
that k grows up to log2n,

k = log2n ⇒ n = 2k

Substitute these values in equation (2)

T(n) = nT(n/n) + log2n . n

T(n) = O(n.log2n) (because, T(1) = 0, from base case)

Master method:

Recurrence of the merge sort, T(n) = 2T(n/2) + n is of the form T(n) =

a.T(n/b) + f(n),

Comparing both the recurrence,

a = 2, b = 2 and f(n) = n with d = 1, where d is the degree of polynomial

function f(n).

bd = 21 = 2 Here, a = bd, so from the Case 1 of Variant – I of master method,

T(n) = O(ndlog2n)

= O(nlog2n)

Whether the list is already sorted, inverse sorted or randomly shuffled, all
three steps must be performed.

Merge sort cannot detect if the list is sorted. So numbers of comparisons are
the same for all three cases.
Time Complexity of Merge Sort

Best Case Complexity: O(n*log n)

Worst Case Complexity: O(n*log n)
Average Case Complexity: O(n*log n)
Space Complexity

The space complexity of merge sort is O(n).

Advantages
 It is quicker for larger lists because unlike insertion and bubble sort it
doesn’t go through the whole list several times.
 It has a consistent running time, carries out different bits with
similar times in a stage.
Disadvantages
 Slower comparative to the other sort algorithms for smaller tasks.
 Goes through the whole process even the list is sorted (just like
insertion and bubble sort?)
 Uses more memory space to store the sub elements of the initial split
list.
Merge Sort Applications
 Inversion count problem
 External sorting
 E-commerce applications

Quick Sort Algorithm

Quick sort is a fast sorting algorithm used to sort a list of elements. Quick sort
algorithm is invented by C. A. R. Hoare.

The quick sort algorithm attempts to separate the list of elements into two
parts and then sort each part recursively. That means it use divide and
conquer strategy.

In quick sort, the partition of the list is performed based on the element
called pivot. Here pivot element is one of the elements in the list.
The list is divided into two partitions such that "all elements to the left of
pivot are smaller than the pivot and all elements to the right of pivot are
greater than or equal to the pivot".

Step by Step Process

In Quick sort algorithm, partitioning of the list is performed using following

steps.

 Step 1 - Consider the first element of the list as pivot (i.e., Element at
first position in the list).
 Step 2 - Define two variables i and j. Set i and j to first and last elements
of the list respectively.
 Step 3 - Increment i until list[i] > pivot then stop.
 Step 4 - Decrement j until list[j] < pivot then stop.
 Step 5 - If i < j then exchange list[i] and list[j].
 Step 6 - Repeat steps 3,4 & 5 until i > j.
 Step 7 - Exchange the pivot element with list[j] element.

Following is the sample code for Quick sort...

Quick Sort Logic
//Quick Sort Logic
void quickSort(int list[10],int first,int last){
int pivot,i,j,temp;

if(first < last){

pivot = first;
i = first;
j = last;
while(i < j){
while(list[i] <= list[pivot] && i < last)
i++;
 while(list[j] && list[pivot])
j--;
if(i < j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}
Complexity of the Quick Sort Algorithm

To sort an unsorted list with 'n' number of elements, need to make ((n-1)+(n-
2)+(n-3)+......+1) = (n (n-1))/2 number of comparisons in the worst case.

If the list is already sorted, then it requires 'n' number of comparisons.

Worst Case : O(n2)

Best Case : O (n log n)
Average Case : O (n log n)

Implementation of Quick Sort Algorithm using C Programming

Language
#include<stdio.h>
#include<conio.h>
void quickSort(int [10],int,int);
void main(){
int list[20],size,i;
printf("Enter size of the list: ");
scanf("%d",&size);
printf("Enter %d integer values: ",size);
for(i = 0; i < size; i++)
scanf("%d",&list[i]);
quickSort(list,0,size-1);
printf("List after sorting is: ");
for(i = 0; i < size; i++)
printf(" %d",list[i]);
getch();
}
void quickSort(int list[10],int first,int last){
int pivot,i,j,temp;
 if(first < last){
pivot = first;
i = first;
j = last;
while(i < j){
while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] > list[pivot])
j--;
if(i <j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}
Quick Sort Analysis-

 To find the location of an element that splits the array into two parts, O(n)
operations are required.
 This is because every element in the array is compared to the partitioning
element.
 After the division, each section is examined separately.
 If the array is split approximately in half (which is not usually), then there
will be log2n splits.
 T(n) = 0, if n = 1

T(n) = T(n/2) + T(n/2) + D(n) + C(n), if n > 1

The first T(n/2) = Cost for solving left sub list

The second T(n/2) = Cost for solving right sub list

D(n) is cost of division, which is constant, i.e. O(1) as the list splitting is
done simply by computing the middle of the array

C(n) is cost of conquer, which is linear, i.e. O(n) as two sub lists each of size
n/2 are merged into bigger sorted array of size n with the help of
maximum n comparisons

So, T(n) = 2T(n/2) + O(1) + O(n)

T(n) = 2T(n/2) + n … (1)

We will derive the time complexity of merge sort using two methods:

 Substitution method
 Master method

Substitution method:

Solving original recurrence for n/2,

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

Substituting this in equation (1),

T(n) = 2[ 2T(n/4) + n/2 ] + n

= 22 T(n/22) + 2n

After k substitutions,

T(n) = 2k T(n/2k) + k.n … (2)

 Division of array creates binary tree, which has height log2n, so let us consider
that k grows up to log2n,

k = log2n ⇒ n = 2k

Substitute these values in equation (2)

T(n) = nT(n/n) + log2n . n

T(n) = O(n.log2n) (because, T(1) = 0, from base case)

 Therefore, total comparisons required are f(n) = n x log2n = O(nlog2n).

Worst Case-

 Quick Sort is sensitive to the order of input data.

 It gives the worst performance when elements are already in the ascending
order.
 It then divides the array into sections of 1 and (n-1) elements in each call.
 Then, there are (n-1) divisions in all.
 Therefore, here total comparisons required are f(n) = n x (n-1) = O(n2).
 Order of Quick Sort in worst case = O(n2)

Advantages of Quick Sort-

The advantages of quick sort algorithm are-

 Quick Sort is an in-place sort, so it requires no temporary memory.
 Quick Sort is typically faster than other algorithms. (because its inner loop
can be efficiently implemented on most architectures)
 Quick Sort tends to make excellent usage of the memory hierarchy like
virtual memory or caches.
 Quick Sort can be easily parallelized due to its divide and conquer nature.

Disadvantages of Quick Sort-

The disadvantages of quick sort algorithm are-

 The worst case complexity of quick sort is O(n2).
 This complexity is worse than O(nlogn) worst case complexity of algorithms
like merge sort, heap sort etc.
 It is not a stable sort i.e. the order of equal elements may not be preserved.