SUBJECT: DESIGN AND ANALYSIS OF ALGORITHM

SUB CODE:23CS501

UNIT-1
 LECTURE NOTES

ON

DESIGN AND ANALYSIS OF ALGORITHMS

III B. Tech I Semester (NRCM-NR23 Regulations)

Mr. P. GANGAIAH, Assistant Professor
Department of Computer Science and Engineering

NARSIMHAREDDY ENGINEERING COLLEGE

(UGC AUTONOMOUS INSTITUTION)
Approved by AICTE, New Delhi & Affiliated to JNTUH, Hyderabad
Accredited by NBA, NAAC with A Grade
Maisammaguda(V), Kompally-500100.
UNIT I:
Introduction- Algorithm definition, Algorithm Specification, Performance Analysis- Space
complexity, Time complexity, Randomized Algorithms.
Divide and conquer- General method, applications - Binary search, Merge sort, Quick sort,
Strassen’s Matrix Multiplication.

Algorithm:
An Algorithm is a finite sequence of instructions, each of which has a clear meaning and can be
performed with a finite amount of effort in a finite length of time. No matter what the input values
may be, an algorithm terminates after executing a finite number of instructions. In addition every
algorithm must satisfy the following criteria:

 Input: there are zero or more quantities, which are externally supplied;
 Output: at least one quantity is produced
 Definiteness: each instruction must be clear and unambiguous;
 Finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will
terminate after a finite number of steps;
 Effectiveness: every instruction must be sufficiently basic that it can in principle be carried out
by a person using only pencil and paper. It is not enough that each operation be definite, but it
must also be feasible.

In formal computer science, one distinguishes between an algorithm, and a program. A program does
not necessarily satisfy the fourth condition. One important example of such a program for a computer
is its operating system, which never terminates (except for system crashes) but continues in a wait
loop until more jobs are entered.

We represent algorithm using a pseudo language that is a combination of the constructs of a

programming language together with informal English statements.

Psuedo code for expressing algorithms:

Algorithm Specification: Algorithm can be described in three ways.

1. Natural language like English: When this way is choused care should be taken, we
shouldensure that each & every statement is definite.

2. Graphic representation called flowchart: This method will work well when the
algorithmis small& simple.

3. Pseudo-code Method: In this method, we should typically describe algorithms as

program,which resembles language like Pascal & Algol.

Pseudo-Code Conventions:

1. Comments begin with // and continue until the end of line.

2. Blocks are indicated with matching braces {and}.

3. An identifier begins with a letter. The data types of variables are not explicitly declared.
4. Compound data types can be formed with records. Here is an
example,Node. Record
{
data type – 1 data-1;
.
.
.
data type – n data –
n;node * link;
}

Here link is a pointer to the record type node. Individual data items of a record
canbe accessed with and period.

5. Assignment of values to variables is done using the assignment statement.

<Variable>:= <expression>;

6. There are two Boolean values TRUE and FALSE.

Logical Operators AND, OR, NOT

Relational Operators <, <=,>,>=, =, !=

7. The following looping statements are employed.

For, while and repeat-until

While Loop:
While < condition > do
{
<statement-1>
.
.
.

<statement-n>
}
For Loop:
For variable: = value-1 to value-2 step step do

{
<statement-1>
.
.
.
<statement-
n>
}
repeat-until:

repeat <statement-1>
.
.
.
 <statement-
n>until<condition>

8. A conditional statement has the following forms.

If <condition> then <statement>

If <condition> then <statement-
1>Else <statement-1>

Case statement:

Cas
e
{ : <condition-1> : <statement-1>
.
.
.
: <condition-n> : <statement-n>
: else : <statement-n+1>

9. Input and output are done using the instructions read & write.

10. There is only one type of

procedure: Algorithm, the heading
takes the form,

Algorithm <Name> (<Parameter lists>)

As an example, the following algorithm fields & returns the maximum of ‘n’ given
numbers:

Algorithm <Name> (<Parameter lists>)

 As an example, the following algorithm fields & returns the maximum of ‘n’
givennumbers:

1. Algorithm Max(A,n)
2. // A is an array of size
n3. {
4. Result := A[1];
5. for I:= 2 to n do
6. if A[I] > Result then
7. Result :=A[I];
8. return
Result;9. }

In this algorithm (named Max), A & n are procedure parameters. Result & I are
Localvariables.

Performance Analysis:

The performance of a program is the amount of computer memory and time needed
to run a program. We use two approaches to determine the performance of a program.
Oneis analytical, and the other experimental. In performance analysis we use
analytical methods, while in performance measurement we conduct experiments.

Time Complexity:
The time needed by an algorithm expressed as a function of the size of a problem
is called the time complexity of the algorithm. The time complexity of a program is the
amount of computer time it needs to run to completion.
The limiting behavior of the complexity as size increases is called the asymptotic
time complexity. It is the asymptotic complexity of an algorithm, which ultimately
determines the size of problems that can be solved by the algorithm.

The Running time of a program

When solving a problem we are faced with a choice among algorithms. The basis for
thiscan be any one of the following:
i. We would like an algorithm that is easy to understand code and debug.
ii. We would like an algorithm that makes efficient use of the
computer’sresources, especially, onethat runs as fast aspossible.

Measuring the running time of a program

The running time of a program depends on factors such as:

1. The input to theprogram.
2. The quality of code generated by the compiler used to create the
objectprogram.
3. The nature and speed of the instructions on the machine used to execute theprogram,
4. The time complexity of the algorithm underlying the program.

Statement S/e Frequency Total

1. Algorithm Sum(a,n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. for I=1 to n do 1 n+1 n+1
5. s=s+a[I]; 1 n n
6. return s; 1 1 1
7. } 0 - 0

The total time will be 2n+3

Space Complexity:
The space complexity of a program is the amount of memory it needs to run
to completion. The space need by a program has the following components:
Instruction space: Instruction space is the space needed to store the
compiled version of the program instructions.
Data space: Data space is the space needed to store all constant and variable
values. Data space has two components:
 Space needed by constants and simple variables in program.
 Space needed by dynamically allocated objects such as arrays and
class instances.
Environment stack space: The environment stack is used to save
information needed to resume execution of partially completed functions.
Instruction Space: The amount of instructions space that is needed depends
on factors such as:
 The compiler used to complete the program into machine code.
 The compiler options in effect at the time of compilation
 The target computer.

The space requirement s(p) of any algorithm p may therefore be written

as,S(P) = c+ Sp(Instance characteristics)
Where ‘c’ is a constant.

Example 2:

Algorithm sum(a,n)
{
s=0.0;
for I=1 to n
dos= s+a[I];
return s;
}

 The problem instances for this algorithm are characterized by n,the number of
elements to be summed. The space needed d by ‘n’ is one word, since it is of type
integer.
 The space needed by ‘a’a is the space needed by variables of tyepe array of
floating point numbers.
 This is atleast ‘n’ words, since ‘a’ must be large enough to hold the ‘n’ elements to
 besummed.
 So,we obtain
Ssum(n)>=(n+s)[ n for a[],one
each for n,I a& s]

Complexity of Algorithms
The complexity of an algorithm M is the function f(n) which gives the running time
and/or storage space requirement of the algorithm in terms of the size ‘n’ of the input
data. Mostly, the storage space required by an algorithm is simply a multiple of the
data size ‘n’. Complexity shall refer to the running time of the algorithm.
The function f(n), gives the running time of an algorithm, depends not only on the
size ‘n’ of the input data but also on the particular data. The complexity function f(n)
for certain cases are:
1. Best Case : The minimum possible value of f(n) is called the best case.

2. Average Case : The expected value of f(n).

3. Worst Case : The maximum value of f(n) for any key possible input.

Asymptotic Notations:
The following notations are commonly use notations in performance analysis
andused to characterize the complexity of an algorithm:

1. Big–OH (O)
2. Big–OMEGA (Ω),
3. Big–THETA (Θ) and
4. Little–OH (o)

Big–OH O (Upper Bound)

f(n) = O(g(n)), (pronounced order of or big oh), says that the growth rate of f(n) is
lessthan or equal (<) that of g(n).

Big–OMEGA Ω (Lower Bound)

f(n) = Ω (g(n)) (pronounced omega), says that the growth rate of f(n) is greater
than orequal to (>) that of g(n).

Big–THETA Θ (Same order)

f(n) = Θ (g(n)) (pronounced theta), says that the growth rate of f(n) equals (=) the
growth rate of g(n) [if f(n) = O(g(n)) and T(n) = Θ (g(n)].

little-o notation
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory
needed,given the problem size n, which is usually the number of items. Informally, saying some
equation f(n) = o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches infinity.
The notation is read, "fof n is little oh of g of n".
Formal Definition: f(n) = o(g(n)) means for all c > 0 there exists some k > 0 such that 0 ≤ f(n) < cg(n)
forall n ≥ k. The value of k must not depend on n, but may depend on c.

Different time complexities

Suppose ‘M’ is an algorithm, and suppose ‘n’ is the size of the input data.
Clearlythe complexity f(n) of M increases as n increases. It is usually the rate of
increase of f(n) we want to examine. This is usually done by comparing f(n) with
some standard functions. The most common computing times are:

O(1), O(log2 n), O(n), O(n. log2 n), O(n2), O(n3), O(2n), n! and nn

Classification of Algorithms
 If ‘n’ is the number of data items to be processed or degree of polynomial or the
size ofthe file to be sorted or searched or the number of nodes in a graph etc.

1 Next instructions of most programs are executed once or at most only a

fewtimes. If all the instructions of a program have this property, we say
that its running time is a constant.

Log n When the running time of a program is logarithmic, the program

getsslightly slower as n grows. This running time commonly occurs in
programs that solve a big problem by transforming it into a smaller
problem, cutting the size by some constant fraction., When n is a million,
log n is a doubled. Whenever n doubles, log n increases by a constant, but
log n does not double until n increases to n2.
n When the running time of a program is linear, it is generally the case that a small amount of
processing is done on each input element. This is the optimal situation for an algorithm
that must process n inputs.

n log n This running time arises for algorithms that solve a problem by breaking
itup into smaller sub-problems, solving then independently, and then
combining the solutions. When n doubles, the running time more than
doubles.

n2 When the running time of an algorithm is quadratic, it is practical for use

only on relatively small problems. Quadratic running times typically
arise in algorithms that process all pairs of data items (perhaps in a
double nestedloop) whenever n doubles, the running time increases
fourfold.

n3 Similarly, an algorithm that process triples of data items (perhaps in a

triple–nested loop) has a cubic running time and is practical for use only
onsmall problems. Whenever n doubles, the running time increases eight
fold.

2n Few algorithms with exponential running time are likely to be

appropriate for practical use, such algorithms arise naturally as “brute–
force” solutions to problems. Whenever n doubles, the running time
squares.
 Numerical Comparison of Different Algorithms

The execution time for six of the typical functions is given below:

n log2 n n*log2n n2 n3 2n
1 0 0 1 1 2
2 1 2 4 8 4
4 2 8 16 64 16
8 3 24 64 512 256
16 4 64 256 4096 65,536
32 5 160 1024 32,768 4,294,967,296
64 6 384 4096 2,62,144 Note 1
128 7 896 16,384 2,097,152 Note 2
256 8 2048 65,536 1,677,216 ????????

Note1: The value here is approximately the number of machine

instructionsexecuted by a 1 gigaflop computer in 5000 years.

Randomized algorithm:

An algorithm that uses random numbers to decide what to do next anywhere in its logic is called
Randomized Algorithm. For example, in Randomized Quick Sort, we use random number to pick the
nex tpivot (or we randomly shuffle the array). Quicksort is a familiar, commonly used algorithm in
which randomness can be useful. Any deterministic version of this algorithm requires O(n2)
time to sort n numbers for some well-defined class of degenerate inputs (such as an already sorted
array), with the specific class of inputs that generate this behavior defined by the protocol for pivot
selection.
However, if the algorithm selects pivot elements uniformly at random, it has a provably high
probability of finishing in O(n log n) time regardless of the characteristics of the input. Typically, this
randomness is used to reduce time complexity or space complexity in other standard algorithms.
 Divide and Conquer

General
Method:

Divide and conquer is a design strategy which is well known to breaking down efficiency barriers. When
the method applies, it often leads to a large improvement intime complexity. For example, from O (n 2)
to O (n log n) to sort theelements.

Divide and conquer strategy is as follows: divide the problem instance into two or more smaller
instances of the same problem, solve the smaller instances recursively, and assemble the solutions to
form a solution of the original instance. The recursion stops when an instance is reached which is too
small to divide. When dividing the instance, one can either use whatever division comes most easily to
hand or invest time in making the division carefully so that the assembly is simplified.

Divide and conquer algorithm consists of two parts:

Divide : Divide the problem into a number of sub problems. The sub problemsare
solvedrecursively.
Conquer : The solution to the original problem is then formed from the solutionsto
the subproblems (patching together theanswers).

Traditionally, routines in which the text contains at least two recursive calls are called divide and
conquer algorithms, while routines whose text contains only one recursive call are not. Divide–and–
conquer is a verypowerful use ofrecursion.

Control Abstraction of Divide and Conquer

A control abstraction is a procedure whose flow of control is clear but whose primary operations are
specified by other procedures whose precise meanings are leftundefined. The control abstraction for
divide and conquer technique is DANDC(P), where P is the problem to be solved.

D AND C (P)
{
if SMALL (P) then return S (p);else
{

divide p into smaller instances p1, p2, …. Pk, k

1;apply

D AND C to each of these sub problems;

return (COMBINE (D AND C (p1) , D AND C
(p2),…., D AND C (pk));
}
}

SMALL (P) is a Boolean valued function which determines

whether the input size is small enough so that the answer
can be computed without splitting. If this is so function ‘S’
is invoked otherwise, the problem ‘p’ into smaller sub
problems. Thesesub problems p1, p2, . . . , pk are solved by
recursive application of DANDC.

11
If the sizes of the two sub problems are approximately equal then the computingtime of DANDC

Where, T (n) is the time for DANDC on ‘n’ inputs

g (n) is the time to complete the answer directly for small inputsandf (n) is the
time forDivide and Combine

Binary Search:

If we have ‘n’ records which have been ordered by keys so that x1 < x2 < … < xn . When we are given a
element ‘x’, binary search is used to find the corresponding element from the list. In case ‘x’ is present,
we have to determine a value ‘j’ suchthat a[j] = x (successful search). If ‘x’ is not in the list then j is to set
to zero (un successful search).

In Binary search we jump into the middle of the file, where we find key a[mid], and compare ‘x’ with
a[mid]. If x = a[mid] then the desired record has been found.If x < a[mid] then ‘x’ must be in that
portion of the file that precedes a[mid], if there at all. Similarly, if a[mid] > x, then further search is only
necessary in that past ofthe file which follows a[mid]. If we use recursive procedure of finding the middle
key a[mid] of the un-searched portion of a file, then every un-successful comparison of‘x’ with a[mid]
will eliminate roughly half the un-searched portion from consideration.

Since the array size is roughly halved often each comparison between ‘x’ and a[mid], and since an array
of length ‘n’ can be halved only about log2n times before reaching a trivial length, the worst case
complexityof Binary search is about log2n
low and high are integer variables such that each time through the loop either ‘x’ is found or low is
increased by at least one or high is decreased by at least one. Thus we have two sequences of integers
approaching each other and eventually low will become greater than high causing termination in a finite
number of steps if ‘x’ is not present.

12
 Example for Binary Search

Let us illustrate binary search on the following 9 elements:

Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101

The number of comparisons required for searching different elements is as follows:

1. Searching for x = 101 low high mid

1 9 5
6 9 7
8 9 8
9 9 9

Number of comparisons =
4
Number of comparisons = 4

2. Searching for x = 82
4. Searching for x = -14

Number of comparisons =
3 Number of comparisons = 3

3. Searching for x = 42

13
 5
found
6 9 7
6 6 6
7 6 not found
low high mi
1 9 d5
6 9 7
8 9 8
found low high mi
1 9 d5
1 4 2
1 1 1
low high mi 2 1 not found
1 9 d

Continuing in this manner the number of element comparisons needed to find each ofnine elements is:

Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101
Comparisons 3 2 3 4 1 3 2 3 4

No element requires more than 4 comparisons to be found. Summing the comparisons needed to find
all nine items and dividing by 9, yielding 25/9 orapproximately 2.77 comparisons per successful search
on the average.

There are ten possible ways that an un-successful search may terminate depending upon the value of x.

14
If x < a[1], a[1] < x < a[2], a[2] < x < a[3], a[5] < x < a[6], a[6] < x < a[7] or
a[7] < x < a[8] the algorithm requires 3 element comparisons to determine that ‘x’is not present. For all
of the remaining possibilities BINSRCH requires 4 element comparisons. Thus the average number of
elementcomparisons for an unsuccessful search is:

(3 + 3 + 3 + 4 + 4 + 3 + 3 + 3 + 4 + 4) / 10 = 34/10 = 3.4

The time complexity for a successful search is O(log n) and for an unsuccessfulsearch is Θ(log n).

Successful un-successful searches

searches
Θ(1), Θ(log n), Θ(log n) Θ(log n)
Best average worst best, average and worst

Analysis for worst case

Let T (n) be the time complexity of Binary

searchThealgorithm sets mid to [n+1 / 2]

Therefore,
T(0) = 0
T(n) = 1 if x = a [mid]
= 1 + T([(n + 1) / 2] – 1) if x < a [mid]
= 1 + T(n – [(n + 1)/2]) if x > a [mid]

Let us restrict ‘n’ to values of the form n = 2K – 1, where ‘k’ is a non-negative integer. The array
alwaysbreaks symmetrically into two equal pieces plus middle element.

2K – 1 -1 2K – 1 -1

2K 1

n 1
Algebraically this is 2K 1 1 = 2K – 1 for K > 1

2 2
Giving,

T(0) = 0
T(2k – 1) = 1 if x = a [mid]
= 1 + T(2K - 1 – 1) if x < a [mid]
= 1 + T(2k - 1 – 1) if x > a [mid]

In the worst case the test x = a[mid] always fails, sow(0)

= 0w(2k – 1) = 1 + w(2k - 1 – 1)
This is now solved by repeated substitution:w(2k – 1)

= 1 + w(2k - 1– 1)

15
 = 1 + [1 + w(2k -2 –1)]
= 1 + [1 + [1 + w(2k - 3 –1)]]
= ........
= ........
= i + w(2k - i – 1)

For i < k, letting i = k gives w(2k –1) = K + w(0) = kBut as 2K – 1 = n,

so K = log2(n + 1), so

w(n) = log2(n + 1) = O(log n)

for n = 2K–1, concludes this analysis of binary search.

Although it might seem that the restriction of values of ‘n’ of the form 2 K–1 weakens the result. In
practice this does not matter very much, w(n) is a monotonic increasing function of ‘n’, and hence the
formula given is a good approximation even when ‘n’ is not of the form 2K–1.

Merge Sort:

Merge sort algorithm is a classic example of divide and conquer. To sort an array, recursively, sort its
left and right halves separately and then merge them. The time complexity of merge mort in the best
case, worst case and average case is O(n log n)and the number of comparisons used is nearly optimal.

This strategy is so simple, and so efficient but the problem here is that there seemsto be no easy way
tomerge two adjacent sorted arrays together in place (The result must be build up in a separate array).

The fundamental operation in this algorithm is merging two sorted lists. Because the lists are sorted,
this canbe done in one pass through the input, if the output is put ina third list.

Algorithm

Algorithm MERGESORT (low, high)

// a (low : high) is a global array to be sorted.
{
if (low < high)
{
mid := (low + high)/2 //finds where to split the set
MERGESORT(low, mid); //sort one subset
MERGESORT(mid+1, high); //sort the other subset
MERGE(low, mid, high); // combine the
results
}
}
 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 objective is to merge these sorted sets into single sorted
// set residing in a (low : high). An auxiliary array B is used.
{
h :=low; i := low; j:= mid + 1; while ((h
<mid) and (J < high)) do
{
if (a[h] < a[j]) then
{
b[i] := a[h]; h := h + 1;
}
els
e
{ 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 + l;
}
for k := low to high do
a[k] := b[k];
}

Example

For example let us select the following 8 entries 7, 2, 9, 4, 3, 8, 6, 1 to illustratemerge sort algorithm:
 Tree Calls of MERGESORT(1, 8)

The following figure represents the sequence of recursive calls that are produced by MERGESORT
when itis applied to 8 elements. The values in each node are the valuesof the parameters low and high.

1, 8

1, 4 5, 8

1, 2 3, 4 5, 6 7, 8

1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8

Tree Calls of MERGE()

The tree representation of the calls to procedure MERGE by MERGESORT is asfollows:

1, 1, 2 3, 3, 4 5, 5, 6 7, 7, 8

1, 2, 4 5, 6, 8

1, 4, 8

Analysis of Merge Sort

We will assume that ‘n’ is a power of 2, so that we always split into even halves, sowe solve for the case
n =2k.

For n = 1, the time to merge sort is constant, which we will be denote by 1. Otherwise, the time to merge
sort ‘n’ numbers is equal to the time to do two recursive merge sorts of size n/2, plus the time to merge,
which is linear. The equation says this exactly:

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

This is a standard recurrence relation, which can be solved several ways. We will solve by substituting
recurrence relation continually on the right–hand side.

We have, T(n) = 2T(n/2) + n

18
Since we can substitute n/2 into this main equation

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

= 4 T(n/4) + n
We have,

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

Again, by substituting n/4 into the main equation, we see that

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

= 8 T(n/8) + n
So we have,

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

Continuing in this manner, we obtain:

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

As n = 2k, K = log2n, substituting this in the above equation

n
T (n) 2log2 k2
k log n . n
T 2

2
= n T(1) + n log n
= n log n + n Representing

this in O notation:

T(n) = O(n log n)

We have assumed that n = 2k. The analysis can be refined to handle cases when ‘n’is not a power of
2. The answer turns out to be almostidentical.

Although merge sort’s running time is O(n log n), it is hardly ever used for main memory sorts. The
main problem is that merging two sorted lists requires linear extra memory and the additional work
spent copying to the temporary array and back, throughout the algorithm, has the effect of slowing
down the sort considerably.The Best and worst case time complexity of Merge sort is O(n logn).

Strassen’s Matrix Multiplication:

The matrix multiplication of algorithm due to Strassens is the most dramatic exampleof divide and
conquer technique (1969).

The usual way to multiply two n x n matrices A and B, yielding result matrix ‘C’ as follows :

for i := 1 to n do
for j :=1 to n do
c[i, j] := 0;
for K: = 1 to n do
c[i, j] := c[i, j] + a[i, k] * b[k, j];

19
This algorithm requires n3 scalar multiplication’s (i.e. multiplication ofsinglenumbers) and n3
scalar additions. So we naturally cannot improve upon.

We apply divide and conquer to this problem. For example let us considers
threemultiplication likethis:
A 11 A 12 B 11 B 12 C 11 C 12

A B B C C

A
22 22 22
21 21 21

Then cij can be found by the usual matrix multiplication algorithm,C11 = A11 . B11

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

This leads to a divide–and–conquer algorithm, which performs nxn matrix multiplication by

partitioning the matrices into quarters and performing eight (n/2)x(n/2) matrix multiplications and
four (n/2)x(n/2) matrix additions.
T(1) = 1
T(n) = 8 T(n/2)

Which leads to T (n) = O (n3), where n is the power of 2.

Strassens insight was to find an alternative method for calculating the Cij, requiring seven (n/2) x (n/2)
matrix multiplications and eighteen (n/2) x (n/2) matrix additions and subtractions:

P = (A11 + A22) (B11 + B22) Q =

(A21 + A22) B11

R = A11 (B12 – B22) S = A22

(B21 - B11) T = (A11 + A12)

B22

U = (A21 – A11) (B11 + B12) V = (A12

– A22) (B21 + B22) C11 = P + S – T + V

C12 = R + T C21 =

Q+ S

C22 = P + R - Q + U.

This method is used recursively to perform the seven (n/2) x (n/2) matrix multiplications, then the
recurrence equation for the number of scalar multiplications performed is:

20
 T(1) = 1
T(n) = 7 T(n/2)

Solving this for the case of n = 2k is easy:

T(2k) = 7 T(2k–1)

= 72 T(2k-2)

= ------
= ------
= 7i T(2k–i)

Put i = k
= 7k T(1)

= 7k

That is, T(n) = 7log2 n

= n lo2g 7

= O(n log 72) = O(2n.81)

So, concluding that Strassen’s algorithm is asymptotically more efficient than the standard algorithm.
In practice, the overhead of managing the many small matrices does not pay off until ‘n’ revolves the
hundreds.

Quick Sort

The main reason for the slowness of Algorithms like SIS is that all comparisons and exchanges between
keys in a sequence w1, w2, , wn take place between adjacent pairs. In this way it takes a relatively long
time for a key that is badly out ofplace to work its way into its proper position in the sortedsequence.

Hoare his devised a very efficient way of implementing this idea in the early 1960’s that improves
theO(n2) behavior of SIS algorithm with an expected performance that is O(n log n).

In essence, the quick sort algorithm partitions the original array by rearranging it into two groups.
The first group contains those elements less than some arbitrary chosen value taken from the set, and
the second group contains those elements greater than or equal to the chosen value.

The chosen value is known as the pivot element. Once the array has been rearrangedin this way with
respect to the pivot, the very same partitioning is recursively applied to each of the two subsets. When
all the subsets have been partitioned and rearranged, the original array is sorted.

The function partition() makes use of two pointers ‘i’ and ‘j’ which are moved toward each other in the
following fashion:

 Repeatedly increase the pointer ‘i’ until a[i] >= pivot.

 Repeatedly decrease the pointer ‘j’ until a[j] <= pivot.

  If j > i, interchange a[j] with a[i]

 Repeat the steps 1, 2 and 3 till the ‘i’ pointer crosses the ‘j’ pointer. If ‘i’ pointer crosses ‘j’
pointer, the position for pivot is found and place pivot element in ‘j’ pointer position.

The program uses a recursive function quicksort(). The algorithm of quick sortfunction sorts
allelements in an array ‘a’ between positions ‘low’ and ‘high’.

 It terminates when the condition low >= high is satisfied. This condition will be satisfied
only when the array is completelysorted.

 Here we choose the first element as the ‘pivot’. So, pivot = x[low]. Now it calls the partition
function to find the proper position j of the element x[low] i.e. pivot. Then we will have two
sub-arrays x[low], x[low+1], . . . .
. . . x[j-1] and x[j+1], x[j+2], x[high].

 It calls itself recursively to sort the left sub-array x[low], x[low+1], . . . . .

. . x[j-1] between positions low and j-1 (where j is returned by the partition
function).

 It calls itself recursively to sort the right sub-array x[j+1], x[j+2], . . . . . .

. . . x[high] between positions j+1 and high.
 Example

Select first element as the pivot element. Move ‘i’ pointer from left to right in search of an element larger
than pivot. Move the ‘j’ pointer from right to left in search of an element smaller than pivot. If such
elements are found, the elements are swapped. This process continues till the ‘i’ pointer crosses the ‘j’
pointer. If ‘i’ pointer crosses ‘j’ pointer, the position for pivot is found and interchange pivot and element
at ‘j’ position.

Let us consider the following example with 13 elements to analyze quick sort:

1 2 3 4 5 6 7 8 9 10 11 12 13 Remarks

38 08 16 06 79 57 24 56 02 58 04 70 45
pivot i j swap i & j
04 79
i j swap i & j
 02 57
j i
swap
(24 08 16 06 04 02) 38 (56 57 58 79 70 45)
pivot&
j
swap
pivot j, i
pivot&j
(02 08 16 06 04) 24
pivot,j swap
i
pivot&j
02 (08 16 06 04)
pivot i j swap i & j
04 16
j i
swap
(06 04) 08 (16)
pivot&j
pivot,j
i
swap
(04) 06
pivot&j
04
pivot,
j, i
16
pivot,
j, i
(02 04 06 08 16 24) 38
(56 57 58 79 70 45)
pivot i j swap i & j
45 57
j i
swap
(45) 56 (58 79 70 57)
pivot&j
45
pivot, swap
pivot&j
j, i
(58 79 57)
70 swap i & j
pivot i j
57 79
j i
swap pivot&
(57) 58 (70 79)
j
57
pivot,
j, i
(70 79)
pivot,j swap pivot&
i
j
70
79
pivot,j,
i
(45 56 57 58 70 79)
02 04 06 08 16 24 38 45 56 57 58 70 79

24
Analysis of Quick Sort:

Like merge sort, quick sort is recursive, and hence its analysis requires solving a recurrence
formula. Wewill do the analysis for a quick sort, assuming a random pivot(and no cut off for small
files).

We will take T (0) = T (1) = 1, as in merge sort.

The running time of quick sort is equal to the running time of the two recursive calls plus the linear
timespent in the partition (The pivot selection takes only constant time). This gives the basic quick sort
relation:

T (n) = T (i) + T (n – i – 1) + C n - (1)

Where, i = |S1| is the number of elements in S1.

Worst Case Analysis

The pivot is the smallest element, all the time. Then i=0 and if we ignore T(0)=1, which is insignificant,
therecurrence is:

T (n) = T (n – 1) + C n n > 1 - (2)

Using equation – (1) repeatedly, thus

T (n – 1) = T (n – 2) + C (n – 1)

T (n – 2) = T (n – 3) + C (n – 2)

----- -- -

T (2) = T (1) + C (2)

Adding up all these equations yields

n
T (n) T (1)

i 2
i

= O (n2) - (3)
Best and Average Case Analysis

The number of comparisons for first call on partition: Assume left_to_right moves over k
smaller element and thus k comparisons. So when right_to_left crosses left_to_right it has made
n-k+1 comparisons. So, first call on partition makes n+1 comparisons. The average case
complexity of quicksort is

T(n) = comparisons for first call on quicksort

+
{Σ 1<=nleft,nright<=n [T(nleft) + T(nright)]}n = (n+1) + 2 [T(0) +T(1) + T(2) +
----- + T(n-1)]/n

nT(n) = n(n+1) + 2 [T(0) +T(1) + T(2) + ---------------------- + T(n-2) +T(n-1)]

(n-1)T(n-1) = (n-1)n + 2 [T(0) +T(1) + T(2) + --------------------------+ T(n-2)] \

Subtracting both sides:

nT(n) –(n-1)T(n-1) = [ n(n+1) – (n-1)n] + 2T(n-1) = 2n + 2T(n-1)nT(n) = 2n

+ (n-1)T(n-1) + 2T(n-1) = 2n +
(n+1)T(n-1) T(n) = 2 + (n+1)T(n-
1)/n
The recurrence relation obtained is:
T(n)/(n+1) = 2/(n+1) + T(n-1)/n

Using the method of subsititution:

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

T(n-1)/n = 2/n + T(n-2)/(n-1)
T(n-2)/(n-1) = 2/(n-1) + T(n-3)/(n-2)
T(n-3)/(n-2) = 2/(n-2) + T(n-4)/(n-3)
. .
. .
T(3)/4 = 2/4 + T(2)/3
T(2)/3 = 2/3 + T(1)/2 T(1)/2 = 2/2 +
T(0)
Adding both sides:
T(n)/(n+1) + [T(n-1)/n + T(n-2)/(n-1) + ---------------------------------- + T(2)/3 + T(1)/2]
= [T(n-1)/n + T(n-2)/(n-1) + ---------------------------- + T(2)/3 + T(1)/2] + T(0)+
[2/(n+1) + 2/n + 2/(n-1) +-------------------------- +2/4 + 2/3]
Cancelling the common terms:
T(n)/(n+1) = 2[1/2 +1/3+1/4+------------------------------+1/n+1/(n+1)]

T(n) = (n+1)2[ 2 k n 1 1/ k
=2(n+1) [ ]
=2(n+1)[log (n+1) – log 2]
=2n log (n+1) + log (n+1)-2n log 2 –log 2
T(n)= O(n log n)