Design and Analysis of Algorithms
UNIT – I
Introduction: Algorithm,
Performance Analysis-Space complexity
Time complexity
Asymptotic Notations- Big oh notation, Omega notation, Theta
notation and Little oh notation.
Divide and conquer: General method applications-Binary search
Quick sort
Merge sort
Strassen’s matrix multiplication.
A Brief History of Algorithm
• The term algorithm got its name from the Persian astronomer and
mathematician, Abu Abdullah Muhammad ibn Musa Al-
Khawarizmi (780 AD), dubbed the father of algebra (al-jabr).
• He was from a Persian city known as Khwarizm, found in present-
day Uzbekistan. The Persian Arabs (or Arabs in general) were
given very common names like Muhammad, Musa, Abdullah, and
so they would (and still) differentiate each other by their location
(city, state, etc). In this context, if John Doe were American, he’d
be known as John Doe al-Amriki, i.e. John Doe the American.
Algorithm
• What is an Algorithm?
• An algorithm is a series of step-by-step instructions that
aim to solve a particular problem.
• The word Algorithm means ” A set of finite rules or
instructions to be followed in calculations or other
problem-solving operations ” Or ” A procedure for solving
a mathematical problem in a finite number of steps that
frequently involves recursive operations”.
INTRODUCTION TO ALGORITHMS
ALGORITHM
Informal Definition:
•An Algorithm is any well-defined computational procedure that takes
some value or set of values as Input and produces a set of values or some
value as output. Thus algorithm is a sequence of computational steps that
transforms the i/p into the o/p.
•Formal Definition: 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.
INTRODUCTION TO ALGORITHMS
Algorithm Design
•The important aspects of algorithm design include creating an efficient algorithm to
solve a problem in an efficient way using minimum time and space.
Note:- In modern era we have large amount of space, so we only care for time not for
space.
Problem Development Steps
The following steps are involved in solving computational
problems.
Problem definition
Development of a model
Specification of an Algorithm
Designing an Algorithm
Checking the correctness of an Algorithm
Analysis of an Algorithm
Implementation of an Algorithm
Program testing
Documentation
Characteristics of Algorithms
The main characteristics of algorithms are as follows :-
i. Input:- Minimum number of input required is zero (0) to run algorithm.
ii. Output:- Minimum number of output required is one. Algo should be produce at list
one output.
iii. Finiteness:- Algo should terminate after finite number of steps.
iv. Effectiveness:- It should be easy to implement in any programming language. Algo
is
language independent.
v. Definiteness:- Algo should be unambiguous.
example:- 2+3*4=14 ← always answer is same.
Algorithm Specification
Algorithm can be described in three ways.
Natural language like English:
should ensure that each & every statement is definite.
Graphic representation called flowchart: This method will work well when the
algorithm is small & simple.
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.
Pseudo-Code Conventions:
4 . Compound data types can be formed with records.
•Here is an example,
Node. Record
{
data type – 1 data-1;
data type – 2 data-2;
.
.
data type – n data – n;
node * link;
}
Pseudo-Code Conventions:
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>
}
Pseudo-Code Conventions:
For Loop:
For variable: = value-1 to value-2 step step do
{ <state ment-1>
.
.
.
<statement-n>
}
repeat -until:
repeat
<statement-1>
.
.
.
<statement-n>
until<condition>
Pseudo-Code Conventions:
8. A conditional statement has the following forms.
If <condition> then <statement>
If <condition> then <statement-1>
Else <statement-1>
Case statement:
Case
{
: <condition-1>:<statement-1>
.
.
.
: <condition-n>:<statement-n>
: else: <statement-n+1>
}
Pseudo-Code Conventions:
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)
Pseudocode for expressing
algorithms
• Pseudocode can be easily understood by someone who has
basic knowledge of programming.
• Pseudocode does not have a specific syntax unlike a program
that is written using syntaxes of a particular language.
• Hence, pseudocode cannot be executed on a computer, rather
it eases the work of a programmer as it can be easily
understood.
Difference between Algorithm and Pseudocode:
algorithm pseudocode
An algorithm has some specific characteristics that A pseudocode on the other hand is not restricted to
describe the process. something. It’s only objective is to represent an
algorithm in a realistic manner.
An algorithm is written in plain English or general A pseudocode is written with a hint of programming
language. concepts such as control structures.
To understand the difference between an algorithm and pseudocode lets have a look into the following exam
Consider an example of calculating the area of a circle.
Algorithm:
[Link].
[Link] r: radius value as the input given by the user.
[Link] the Area: 3.14 * r * r.
[Link] the Area.
[Link].
Pseudocode:
AreaofCircle()
{
BEGIN
Read: Number radius, Area;
Input r;
Area = 3.14 * r * r;
Output Area;
END
}
Advantages of Pseudocode:
•Pseudocode improves the readability and is the best way to start implementing an algorithm.
•A pseudocode works as a rough documentation. It makes the work of a programmer easy as it helps them
understand the code better.
•It acts as a bridge between a program and an algorithm.
•It makes the process of constructing a code easy.
Pseudo-Code Conventions:
As an example, the following algorithm fields & returns the maximum of ‘n’
given numbers:
1 Algorithm Max(A, n)
2 // A is an array of size n
3 {
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 Local variables.
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. One is analytical, and the other experimental.
• In performance analysis we use analytical methods, while in
performance measurement we conduct experiments.
Performance Analysis
1. Space Complexity:
The space complexity of an algorithm is the amount of memory it
needs to run to compilation.
2. Time Complexity:
The time complexity of an algorithm is the amount of computer time
it needs to run to compilation.
Performance Analysis
1. Space Complexity
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.
Space Complexity Example 1:
Algorithm abc(a,b,c)
{
return a+b++*c+(a+b-c)/(a+b) +4.0;
}
S(p) = 3
c: a, b, c
Performance Analysis
Example 2:
Algorithm sum(a,n)
{
s=0.0;
for I=1 to n do s= s+a[I];
return s;
}
S(P) = 3 + n c: s,I,n
sp:a[]
Performance Analysis
2. Time Complexity
•Step count method: step count of an algorithm is to build a table in which we list
the total number of steps contributes by each statement.
•First determine the number of steps per execution (s/e) of the statement and the
total number of times (ie., frequency) each statement is executed.
•By combining these two quantities, the total contribution of all statements, the step
count for the entire algorithm is obtained.
Asymptotic Notations
• The efficiency of an algorithm depends on the amount of time,
storage and other resources required to execute the algorithm.
• The efficiency is measured with the help of asymptotic
notations.
• An algorithm may not have the same performance for different
types of inputs. With the increase in the input size, the
performance will change.
• The study of change in performance of the algorithm with the
change in the order of the input size is defined as asymptotic
analysis.
Asymptotic Notations
• Asymptotic notations are the mathematical notations used to
describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
• For example: In bubble sort, when the input array is already sorted,
the time taken by the algorithm is linear i.e. the best case.
• But, when the input array is in reverse condition, the algorithm
takes the maximum time (quadratic) to sort the elements i.e. the
worst case.
• When the input array is neither sorted nor in reverse order, then it
takes average time. These durations are denoted using asymptotic
notations.
Asymptotic Notations
best case
average case
There are mainly three asymptotic
worst case
120
notations: 100
Running Time
80
Big-O notation 60
Omega notation 40
20
Theta notation 0
1000 2000 3000 4000
I nput Size
Asymptotic Notations
• Big-O Notation (O-notation):Big-O notation represents the upper bound of
the running time of an algorithm. Thus, it gives the worst-case complexity
of an algorithm.
• Big-O gives the upper bound of a function
• F(n)<= c*g(n) where f(n) and g(n) are two
Non-negative functions.
O(g(n)) = { f(n): there exist positive
constants c and n0 such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
Asymptotic Notations
• Omega Notation (Ω-notation) : Omega notation represents the lower
bound of the running time of an algorithm. Thus, it provides the best case
complexity of an algorithm.
• Omega gives the lower bound of a function
• Ω(g(n)) = { f(n): there exist positive
constants c and n0 such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
f(n) ≥ c*g(n)
Asymptotic Notations
Theta Notation (Θ-notation): Theta notation encloses the function from
above and below. Since it represents the upper and the lower bound of the
running time of an algorithm, it is used for analyzing the average-case
complexity of an algorithm.
Theta bounds the function within constants factors
• For a function g(n), Θ(g(n)) is given by the
relation:
• Θ(g(n)) = { f(n): there exist positive
constants c1, c2 and n0 such that
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }
C1*g(n) ≤ f(n) ≤ c2*g(n)
Strassen’s MatrixMultiplication
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’s MatrixMultiplication
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.
Strassen’s MatrixMultiplication
void multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
Time Complexity of above method is O(N 3).
Strassen’s MatrixMultiplication
Divide and Conquer
Following is simple Divide and Conquer method to
multiply two square matrices.
Divide matrices A and B in 4 sub-matrices of size
N/2 x N/2 as shown in the below diagram.
Calculate following values recursively. ae + bg, af +
bh, ce + dg and cf + dh.
Strassen’s MatrixMultiplication
Strassen’s MatrixMultiplication
In the above method, we do 8 multiplications for
matrices of size N/2 x N/2 and 4 additions.
Addition of two matrices takes O(N ) time.
2
So the time complexity can be written as
T(N) = 8T(N/2) + O(N
2
) From Master's Theorem, time
complexity of above method is O(N ) 3
Strassen’s MatrixMultiplication
In the above divide and conquer method, the main
component for high time complexity is 8 recursive calls.
The idea of Strassen’s method is to reduce the number of
recursive calls to 7.
Strassen’s method is similar to above simple divide and
conquer method in the sense that this method also divide
matrices to sub-matrices of size N/2 x N/2 as shown in the
above diagram, but in Strassen’s method, the four sub-
matrices of result are calculated using following formulae.
Strassen’s MatrixMultiplication
Strassen’s MatrixMultiplication
Time Complexity of Strassen’s Method
Addition and Subtraction of two matrices takes O(N ) time.
2
So time complexity can be written as
T(N) = 7T(N/2) + O(N )
2
From Master's Theorem, time complexity
of above method is O(NLog7) which is
approximately O(N2.8074)