NEW HORIZON INSTITUTE OF TECHNOLOGY AND

MANAGEMENT

DEPARTMENT OF COMPUTER SCIENCE AND DESIGN

SUBJECT: DESIGN AND ANALYSIS OF ALGORITHMS

II B.TECH II- SEM

By
Susmitha Mandava
Assistant Professor
CSD
 SYLLABUS
UNIT – I

INTRODUCTION: Performance analysis, space, and time

complexity Growth of function, Big-Oh, Omega Theta notation
Mathematical background for algorithm analysis.
Complexity class: Definition of P, NP, NP-Hard, NP-Complete
Analysis of selection sort, insertion sort.
Recurrences: The substitution method, Recursion tree method,
Master method

UNIT – II
Divide and Conquer Approach: General method, Merge sort,
Quick sort, Finding minimum and maximum algorithms and their
Analysis, Analysis of Binary search.
 UNIT - III
Greedy Method Approach :General Method, Single
source shortest path: Dijkstra Algorithm Fractional
Knapsack problem, Job sequencing with deadlines,
Minimum cost spanning trees: Kruskal and Prim‟s
algorithms

UNIT – IV
Dynamic Programming Approach: General
Method, Multistage graphs, Single source shortest
path: Bellman Ford Algorithm All pair shortest path:
Floyd Warshall Algorithm, Assembly-line scheduling
Problem0/1 knapsack Problem, Travelling
Salesperson problem, Longest common
subsequence
 UNIT - V
Backtracking and Branch and bound: General Method,
Backtracking: N-queen problem, Sum of subsets, Graph
coloring
Branch and Bound: Travelling Salesperson Problem, 15
Puzzle problem
UNIT - VI
String Matching Algorithms: The Naïve string-matching
algorithm, The Rabin Karp algorithm, The Knuth-Morris-Pratt
algorithm

TEXT BOOKS
1. T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein,
“Introduction to algorithms”, 2nd Edition, PHI Publication
2005
2. Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals
of computer algorithms” University Press
 REFERENCES
 Sanjoy Dasgupta, Christos Papadimitriou, Umesh
Vazirani, “Algorithms”, Tata McGrawHill Edition
 S. K. Basu, “Design Methods and Analysis of
Algorithm”, PHI
 INTRODUCTION
The word algorithm comes from the name of the person author
-Abu Jafar Mohammed Ibn Musa Al khowarizmi who wrote
A text book entitled-”Algorithmi de numero indorum” Now term” Algorithmi
”in the title of the book led to the term Algorithm.

An algorithm is an effective method for finding out the solution for a given
problem. It is a sequence of instruction
That conveys the method to address a problem

Algorithm : Step by step procedure to solve a computational problem is

called Algorithm.
or
An Algorithm is a step-by-step plan for a computational procedure
that possibly begins with an input and yields an output value in a finite
number of steps in order to solve a particular problem.
 INTRODUCTION

 An algorithm is a set of steps of operations to solve a problem

performing calculation, data processing, and automated reasoning
tasks.

 An algorithm is an efficient method that can be expressed within finite

amount of Time and space.

 The important aspects of algorithm design include creating an efficient

algorithm to solve a problem in an efficient way using minimum time
and space.

 To solve a problem, different approaches can be followed. Some of

them can be efficient with respect to time consumption, whereas other
approaches may be memory efficient.
 PROPERTIES OF ALGORITHM

TO EVALUATE AN ALGORITHM WE HAVE TO SATISFY THE FOLLOWING

CRITERIA:

1.INPUT: The Algorithm should be given zero or more input.

2.OUTPUT: At least one quantity is produced. For each input the algorithm
produced value from specific task.

3.DEFINITENESS: Each instruction is clear and unambiguous.

4.FINITENESS: If we trace out the instructions of an algorithm, then for all cases,
the algorithm terminates after a finite number of steps.

5.EFFECTIVENESS: Every instruction must very basic so that it can be carried

out, in principle, by a person using only pencil & paper.
 ALGORITHM (CONTD…)

 A well-defined computational procedure that takes some value, or

set of values, as input and produces some value, or set of values,
as output.

 Written in a pseudo code which can be implemented in the

language of programmer’s choice.

PSEUDO CODE: A notation resembling a simplified programming

language, used in program design.
 How To Write an Algorithm
Step-1:start Step-1: start
Step-2:Read a,b,c Step-2: Read a,b,c
Step-3:if a>b Step-3:if a>b then go to step 4
if a>c otherwise go to step 5
print a is largest Step-4:if a>c then
else print a is largest otherwise
if b>c print c is largest
print b is largest Step-5: if b>c then
else print b is largest otherwise
print c is largest print c is largest
Step-4 : stop step-6: stop
 Differences
Algorithm Program
1.At design phase 1.At Implementation phase
2.Natural language 2.written in any
programming language
3.Person should have 3.Programmer
Domain knowledge
4.Analyze 4.Testing
 ALGORITHM SPECIFICATION
Algorithm can be described (Represent) in four ways.

1.Natural language like English:

When this way is chooses, care should be taken, we
should ensure that each & every statement is definite.
(no ambiguity)

2. Graphic representation called flowchart:

This method will work well when the algorithm is small&
simple.
3. Pseudo-code Method:
In this method, we should typically describe algorithms as program,
which resembles language like Pascal & Algol(Algorithmic Language).
4.Programming Language:
we have to use programming language to write algorithms like
C, C++,JAVA etc.
 Issue in the study of algorithm
1. How to create an algorithm.
2. How to validate an algorithm.
3. How to analyses an algorithm
4. How to test a program.

1 .How to create an algorithm: To create an algorithm we have following design

technique
a) Divide & Conquer
b) Greedy method
c) Dynamic Programming
d) Branch & Bound
e) Backtracking
2.How to validate an algorithm: Once an algorithm is created it
is necessary to show that it computes the correct output for all possible
legal input , this process is called algorithm validation.
3.How to analyses an algorithm: Analysis of an algorithm or
performance analysis refers to task of determining how much computing
Time & storage algorithms required.
a) Computing time-Time complexity: Frequency or Step count method
b) Storage space- To calculate space complexity we have to use number
of input used in algorithms.
4.How to test the program: Program is nothing but an expression
for the algorithm using any programming language. To test a program
we need following
a) Debugging: It is processes of executing programs on sample data sets
to determine whether faulty results occur & if so correct them.
b) Profiling or performance measurement is the process of executing a
correct program on data set and measuring the time & space it takes
to compute the result.
 ANALYSIS OF ALGORITHM
PRIORI POSTERIORI
1.Done priori to run algorithm 1.Analysis after running
on a specific system it on system.
2.Hardware independent 2.Dependent on hardware
3.Approximate analysis 3.Actual statistics of an
algorithm
4.Dependent on no of time 4.They do not do posteriori
statements are executed analysis
Problem: Suppose there are 60 students in the class. How will
you calculate the number of absentees in the class?
Pseudo Approach
1.Initialize a variable called as Count to zero, absent to
zero, total to 60
2.FOR EACH Student PRESENT DO the following:
Increase the Count by One
3.Then Subtract Count from total and store the result
in absent
4.Display the number of absent students
Problem: Suppose there are 60 students in the class. How will
you calculate the number of absentees in the class?
Algorithmic Approach:
1.Count <- 0, absent <- 0, total <- 60
2.REPEAT till all students counted
Count <- Count + 1
3.absent <- total - Count
4.Print "Number absent is:" , absent
 Need of Algorithm
1. To understand the basic idea of the problem.
2. To find an approach to solve the problem.
3. To improve the efficiency of existing techniques.
4. To understand the basic principles of designing the
algorithms. To compare the performance of the algorithm
with respect to other techniques.
6. It is the best method of description without describing the
implementation detail.
7. The Algorithm gives a clear description of requirements
and goal of the problem to the designer.
8. A good design can produce a good solution.
9. To understand the flow of the problem.
 PERFORMANCE ANALYSIS
Analysis of Algorithm: Algorithm analysis in AOA involves evaluating the
efficiency and performance of algorithms. It helps in understanding how different
algorithms behave under varying conditions.

Performance Analysis: An algorithm is said to be efficient and fast if it take

less time to execute and consumes less memory space at run time is called
Performance Analysis.
1.SPACE COMPLEXITY:
The space complexity of an algorithm is the amount of Memory Space
required by an algorithm during course of execution is called space complexity
.There are three types of space
a)Instruction space :executable program
b)Data space: Required to store all the constant and variable data space.
c)Environment: It is required to store environment information needed to resume the
suspended space.
2. TIME COMPLEXITY:
The time complexity of an algorithm is the total amount of time required
by an algorithm to complete its execution.
 Space complexity
Now there are two types of space complexity

a) Constant space complexity

b) Linear(variable)space complexity
1.Constant space complexity: A fixed amount of space for
all the input values.

Example : int square(int a)

{
return a*a;
}
Here algorithm requires fixed amount of space for all
the input values.
2.Linear space complexity: The space needed for
algorithm is based on size.
 Size of the variable ‘n’ = 1 word
 Array of a values = n word
 Loop variable = 1 word
 Sum variable = 1 word
Example:
int sum(int A[],int n)
{ n
int sum=0,i; 1
for (i=0;i<n;i++) 1
Sum=sum+A[i]; 1
Return sum;
} Ans : 1+n+1+1 = n+3 words
Examples:
1.Algorithm sum(a,,b,c)
{
a=10; a-1
b=20; b-1
c=a+b; c-1
}
s(p)=c+sp
3+0=3
0(n)=3
2. algorithm sum(a,n)
{
total-=0; -1
Fori=1 to n do -1,1
Total=total+a[i]--n
Return total
 DAA

Algorithm-1 Algorithm-2 Algorithm-3:recursive procedure

DAA
1.Constant time complexity : If a program required fixed
amount of time for all input values is called Constant
time complexity .

Example : int sum(int a , int b)

{
return a+b;
}
2.Linear time complexity: If the input values are
increased then the time complexity will changes.
 comments = 0 step
 Assignment statement= 1 step
 condition statement= 1 step
 loop condition for n times = n+1 steps
 body of the loop = n steps
Example : int sum(int A[],int n)
{
int sum=0,i;
for (i=0;i<n;i++)
sum=sum+A[i];
return sum;
cost repetation total
1 1 1
1+1+1 1+(n+1)+n 2n+2
2 n 2n
1 1 1
4n+4
DAA
 TIME COMPLEXITY

The time T(p) taken by a program P is the sum of the

compile time and the run time(execution time)
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

Total 2n+3
 KINDS OF ANALYSIS

1.Worst-case: (usually)
• T(n) = maximum time of algorithm on any input of size n.

2.Average-case: (sometimes)
• T(n) = expected time of algorithm over all inputs of size n.
• Need assumption of statistical distribution of inputs.

3.Best-case:
• T(n) = minimum time of algorithm on any input of size n.

COMPLEXITY:
Complexity refers to the rate at which the storage time grows as a
function of the problem size
 Analysis of an Algorithm
 The goal of analysis of an algorithm is to compare
algorithm in running time and also Memory
management.
 Running time of an algorithm depends on how long it
takes a computer to run the lines of code of the
algorithm.
Running time of an algorithm depends on
1.Speed of computer
2.Programming language
3.Compiler and translator
Examples: binary search, linear search
 ASYMPTOTIC ANALYSIS:
 Expressing the complexity in term of its relationship
to know function. This type analysis is called
asymptotic analysis.
The main idea of Asymptotic analysis is to have a
measure of efficiency of an algorithm , that doesn’t
depends on
1.Machine constants.
2.Doesn’t require algorithm to be implemented.
3.Time taken by program to be prepare.
 ASYMPTOTIC NOTATION

ASYMPTOTIC NOTATION: The mathematical way of

representing the Time complexity.
The notation we use to describe the asymptotic running time of
an algorithm are defined in terms of functions whose domains
are the set of natural numbers.

Definition : It is the way to describe the behavior of functions in

the limit or without bounds.
Asymptotic growth: The rate at which the function grows…
“growth rate” is the complexity of the function or the amount of
resource it takes up to compute.

Growth rate Time +memory

 Classification of growth
1.Growing with the same rate.
2. Growing with the slower rate.
3.Growing with the faster rate.
They are 3 asymptotic notations are mostly used to
represent time complexity of algorithm.

1.Big oh (O)notation
2.Big omega (Ω) notation
3.Theta(Θ) notation
4.Little oh notation
5.Little omega(Ω) notation
 1.Big oh (O)notation
1.Big oh (O)notation : Asymptotic “less than”(slower rate).This
notation mainly represent upper bound of algorithm run time.
Big oh (O)notation is useful to calculate maximum amount of time of
execution.
By using Big-oh notation we have to calculate worst case time complexity.
Formula : f(n)<=c g(n) n>=n0 , c>0 ,n0 >=1

Definition: Let f(n) ,g(n) be two non negative (positive) function

now the f(n)=O(g(n)) if there exist two positive constant c,n0 such that
f(n)<= c.g(n) for all value of n>0 & c>0
 1.Big O-notation

 For a given function g (n) , we denote by O( g (n)) the set

of functions
 f (n) : there exist positive constants c and n0 s.t.
O( g (n))   
 0  f ( n)  cg ( n) for all n  n 0 

 We use O-notation to give an asymptotic upper bound of

a function, to within a constant factor.
 f (n)  O( g (n)) means that there existes some constant c
s.t. f (n) is always  cg(n) for large enough n.
 Examples
Example : f(n)=2n +3 & g(n)= n
Formula : f(n)<=c g(n) n>=n0 , c>0 ,n0 >=1
f(n)=2n+3 & g(n)=n
Now 3n+2<=c.n
3n+2<=4.n
Put the value of n =1
5<=4 false
N=2 8<=8 true now n0>2 For all value of n>2 & c=4
now f(n)<= c.g(n)
3n+2<=4n for all value of n>2
Above condition is satisfied this notation takes maximum amount of time to
execute .so that it is called worst case complexity.
 2.Ω-Omega notation
Ω-Omega notation : Asymptotic “greater than”(faster rate).
It represent Lower bound of algorithm run time.
By using Big Omega notation we can calculate minimum amount of
time. We can say that it is best case time complexity.
Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0 >=1
where c is constant, n is function
 Lower bound
 Best case
 Ω-Omega notation

 For a given functiong (n) , we denote by ( g ( n)) the

set of functions

 f (n) : there exist positive constants c and n0 s.t.

( g (n))   
 0  cg (n)  f (n) for all n  n0 
 We use Ω-notation to give an asymptotic lower bound on
a function, to within a constant factor.
 f (n)  ( g (n)) means that there exists some constant c s.t.
f (n) is always  cg (n) for large enough n.
 Examples
Example : f(n)=3n +2
Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0 >=1
f(n)=3n+2
3n+2>=1*n, c=1 put the value of n=1
n=1 5>=1 true n0>=1 for all value of n
It means that f(n)= Ω g(n).
 3. -Theta notation
Theta (Θ) notation : Asymptotic “Equality”(same rate).
It represent average bond of algorithm running time.
By using theta notation we can calculate average amount of time.
So it called average case time complexity of algorithm.
Formula : c1 g(n)<=f(n)<=c2 g(n)

where c is constant, n is function

Average bound
 Θ -Theta notation

 For a given function g (n), we denote by ( g (n)) the set

of functions

 f (n) : there exist positive constants c1 , c2 , and n0 s.t.

( g (n))   
 0  c1 g (n)  f (n)  c2 g (n) for all n  n0 

 A function f (n) belongs to the set ( g (n)) if there exist

positive constants c1 and c2 such that it can be “sand-
wiched” between c1 g ( n) and c2 g (n) or sufficienly large n.
 f (n)  ( g (n)) means that there exists some constant c1
and c2 s.t. c1 g (n)  f (n)  c 2 g (n) for large enough n.
 Examples
Example : f(n)=3n+2
Formula : c1 g(n)<=f(n)<=c2 g(n)
f(n)=2n+3
1*n<=3n+2<=4*n now put the value of
n=1 we get 1<=5<=4 false
n=2 we get 2<=8<=8 true
n=3 we get 3<=11<=12 true
Now all value of n>=2 it is true above condition is satisfied.
 4.Little oh notation
 Little o notation is used to describe an upper bound
that cannot be tight. In other words, loose upper
bound of f(n).
Slower growth rate
f(n) grows slower than g(n)
 Let f(n) and g(n) are the functions that map positive
real numbers. We can say that the function f(n) is
o(g(n)) if for any real positive constant c, there exists
an integer constant n0 ≤ 1 such that f(n) > 0.
Using mathematical relation, we can say that f(n) =
o(g(n)) means,
if

Example on little o asymptotic notation:

1.If f(n) = n2 and g(n) = n3 then check whether

f(n) = o(g(n)) or not.
 Sol:

The result is 0, and it satisfies the equation mentioned

above. So we can say that f(n) = o(g(n)).
 5.Little omega(ω) notation
 Another asymptotic notation is little omega notation.
it is denoted by (ω).
 Little omega (ω) notation is used to describe a loose
lower bound of f(n).
 Faster growth rate
 F(n) grows faster than g(n)
∞
 If
∞

Formally stated as f(n)=ωg(n)

 Example of asymptotic notation

Problem:-Find upper bond ,lower bond & tight bond range for
functions: f(n)= 2n+5
Solution:-Let us given that f(n)= 2n+5 , now g(n)= n
lower bond=2n, upper bond =3n, tight bond=2n
For Big –oh notation(O):- according to definition
f(n)<=cg(n) for Big oh we use upper bond so
f(n)=2n+5, g(n)=n and c=3 according to definition
2n+5<=3n
Put n=1 7<=3 false Put n=2 9<=6 false Put n=3 14<=9 false
Put n=4 13<=12 false Put n=5 15<=15 true
now for all value of n>=5 above condition is satisfied. C=3 n>=5
2. Big - omega notation :- f(n)>=c.g(n) we know that this
Notation is lower bond notation so c=2
Let f(n)=2n+5 & g(n)=2.n
Now 2n+5>=c.g(n);
2n+5>=2n put n=1
We get 7>=2 true for all value of n>=1,c=2 condition is satisfied.
3. Theta notation :- according to definition
c1.g(n)<=f(n)<=c2.g
1/30/2025
 PROBLEM:

PROBLEM “A computational problem specifies an input-output

relationship.”

i.e. What does the input look like ?

What should the output be for each input ?

Example : Input : A list of names of people

Output : The same list sorted alphabetically

Example: Input : A picture in digital format

Output : A description of what the picture shows
Problem v/s Algorithm v/s Program
Aim - To convert centimetres to meters

PROBLEM ALGORITHM PROGRAM

we need to solve a An algorithm specifies A program is a
computer
computational problem how to solve a problem executable
description of
an
algorithm
Input : length in cm 1.Read cm
#include<stdio.h>
Output : length in m 2.Calculate m=cm*0.01 #include<conio.h>
3.Print m void main()
{
float
cm,m;

scanf(“%f”,&cm);

m=cm*0.01;
1/30/2025
Types Of Problems:

1.Tractable
2. Intractable
3. Decision
4. Optimization

1.Tractable Problems: that can be solved in a reasonable ( polynomial ) time

2. Intractable Problems that cannot be solved in a reasonable time

3. Decision Problems that tries to answer a yes/no question

4. Optimization Problems that tries to find an optimal solution Types of

Problems
1/30/2025
 Computational Complexity : The amount of resources
required to run an Algorithm”. Depending on computational
complexity of various problems,the problems can be classified
into 2 groups

Computational complexity problems

P class NP class

NP complete NP hard

1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
Recurrence Relations:
• In previous lectures we have discussed asymptotic analysis of
algorithms and various properties associated with asymptotic
notation.
• As many algorithms are recursive in nature, it is natural to
analyze algorithms based on recurrence relations.
• Recurrence relation is a mathematical model that captures the
underlying time-complexity of an algorithm.
• Three Types of Recurrence Relations
• Substitution method
• Recurrence tree method
• Master theorem
• Solutions to recurrence relations yield the time-complexity of
underlying algorithms.

1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
1/30/2025
 ANALYSIS OF INSERTION-SORT(CONTD.)

•The worst case: The array is reverse sorted

(tj =j for j=2,3, ...,n).
n n(n  1)
j
j 1 2
T (n)  c1n  c2 (n  1)  c5 (n(n  1) / 2  1)
 c6 (n(n  1) / 2)  c7 (n(n  1) / 2)  c8 (n  1)

 (c5 / 2  c6 / 2  c7 / 2)n 2  (c1  c2  c4  c5 / 2  c6 / 2  c7 / 2  c8 )n

T (n)  an2  bn  c