Design and analysis of Algorithm By Dr. B. J. Mohite

Design and Analysis of Algorithms
• Objectives
To understand and learn advance algorithms
and methods used in computer science to
create strong logic and problem solving
approach in student
Ref. Book.
Fundamentals of Computer Algorithms by- Sartaj Sahni
Prof. B. J. Mohite @ Sinhgad Institute of Business Management, Kamlapur

Key terms under study
• Problem
• Computer Science
• Analysis
• Design
• Algorithm, pseudo code and Flowchart

Algorithm ?...
• Persian author, Abu Ja’far Mohammed abn Musa al
Khowarizmi
• Definition:
• Algorithm must satisfy following criteria:
– Input: (Instance)
– Output
– Definiteness
– Finiteness
– Effectiveness
• Algorithms that are definite & effective are also called as
Computational procedures. (OS)

Algorithm
• Advantages
– General Purpose tool
– Independent
– Help in programming
– Help in debugging
– Easiness
• Disadvantages
– Time
– Branching & looping
– Ambiguity
– Synonyms
– No standard method
of wording and
writing of algorithm
text.

Why Algorithms ?...
The study of algorithms includes many
important and active areas of research like –
– How to devise algorithms
– How to validate algorithm
– How to analyze algorithm
– How to test a program.

Pseudo code Conventions…

Algorithm Analysis
• Process of finding diff. resources required
• To make judgment of some instances like
– Does it do what we want it to do?
– Does it work correctly according to the original
specifications of the task?
– Is there documentation that describes how to use it and
how it works?
– Are procedures created in such a way that they perform
logical sub-functions?
– Is the code readable?
– What amount of computational time required?
– What amount of memory space required?

Performance Evaluation
• Priori estimates refer as Performance Analysis
• Posterior testing refer as Performance
measurement.
• RAM – PE model – instructions are executed
one after another, with no concurrent
operations.

Performance Analysis
• Branch of CS called as Complexity theory
• Focus on obtaining estimates of Time and
Space required for particular operation, that
are machine independent.

Space Complexity
• Of an Algo. Is the amount of memory space it
needs to-run-to completion of the process.
• Efficiency inversely proportional to memory
• Space complexity can be calculated by
considering Data & its Size and measured on
WORD

Space needed by any Algo is the Sum of -
– A fixed part that is independent of the characteristics (e.g.
number, size) of the inputs and outputs. This part typically
includes the instruction space (i.e. space for code), space for
simple variable and fixed size component variables (also called
aggregates), space for constants, and so on.
– A variable part that consists of the space needed by component
variables whose size is dependent on the particular problem
instance being solved, the space needed by referenced
variables, and the recursion stack space.

The space requirements S(P) of any algorithm p
may therefore written as –
S(P)= c + Sp(instance characteristics)
Where, c is a constant and fixed variables.

Example :
Algorithm abc( a, b, c)
{
return a+b+c /(a+b) +7.0;
}
Space complexity for the given algorithm = c +
Sp(instance characteristics)
= 4 + 0
= 4 word.

Example :
Algorithm Sum(a,n)
{
s:=0.0;
for i:= 1 to n do
s:= s+ a[i];
return s;
}
Space complexity for the given algorithm
= c + Sp(instance characteristics)
= (3 + n) word.
(n for a[], one each for i, s and n)

Example :
Algorithm RSum(a,n)
{ if n≤ 0 then return a[n];
else return RSum(a, n-1)+ a[n];
}
Space complexity for the given algorithm
= c + Sp (instance characteristics)
= 3 +3(n+1)
=3n+6
= n+2 words.

Time Complexity
• Defn.
• T(P)=Compile time +Run(Execution) Time
• To calculate time complexity, only Run
(Execution) time is taken into consideration.

• introduce a new variable, count, into a program by
identifying Program Step and by Increment the
value of count by appropriate amount with respect
to a statement in the original program executes.
• Program Step - A synthetically meaningful segment of a
program that requires execution time which is independent
on the instance characteristics.
Count method to calculate time complexity

• The number of steps in any program depends on the kind
of statements. For example –
– Comments count as zero steps
– An assignment statement which does not involves any calls to other
algorithm is counted as one step.
– For looping statements the step count equals to the number of step counts
assignable to goal value expression. And should be incremented by one
within a block and after completion of block.
– For conditional statements the step count should incremented by one before
condition statement.
– A return statement is counted as one step and should be write before return
statement.
Count method to calculate time complexity…

For example –
Algorithm Sum(a,n)
{ s:=0;
for i:=1 to n do
{ s:=s+a[i];
}
return s;
}

Algorithm Sum(a,n) // After Adding Count
{ s:=0;
count:=count+1; // for assignment statement execution
for i:=1 to n do
{
count:=count+1; //for For loop Assignment
s:=s+a[i];
count:=count+1;// for addition statement execution
}
count:=count+1; // for last time of for
count:=count+1; // for the return
return s;
}

Algorithm Sum(a,n) //Simplified version for algorithm Sum
{ for i:=1 to n do
{
count:=count+2;
}
count:=count+3;
}
Form above example,
Total number of program steps= 2n + 3, where n is
the loop counter.

Algorithm RSum(a,n)
{
if n ≤ 0 then
return a[n];
else
return RSum(a, n-1) + a[n];
}

Algorithm RSum(a,n)
{
count:=count + 1; // for the if condition
if n ≤ 0 then
{ count:=count + 1;// for the return statement
return a[n];
}
else
{ count:=count + 1; // for the addition, function invoked & return
return RSum(a, n-1) + a[n];
}
}

Algorithm RSum(a,n) //Simplified version of algorithm RSum
with counting’s only
{
count:=count + 1;
if n ≤ 0 then
count:=count + 1;
else
count:=count + 1;
}

Therefore we can write,
• tRSum(n) = 2 if n=0 and
• tRSum(n) = 2+ tRSum(n-1) if n>0
= 2+ 2+ tRSum(n – 2)
= 2(2)+ tRSum(n – 2)
=3 (2) + tRSum(n – 3)
:
:
= n(2) + tRSum(0)
=2n+2
So, the step count for RSum algorithm is 2n+2.Prof. B. J. Mohite @ Sinhgad Institute of Business Management, Kamlapur

Table method to calculate time complexity
• build a table in which we list the total number of steps
contributed by each statement. This table contents three
columns –
– Steps per execution (s/e)- contents count value by which count
increases after execution of that statement.
– Frequency – is the value indicating total number of times
statement executes
– Total steps – can be obtained by combining s/e and frequency.
Total step count can be calculated by adding total steps
contribution values.

Statement s/e Frequency Total
steps
Algorithm Sum(a,n)
{
s:=0;
for i:=1 to n do
s:=s+a[i];
return s;
}
0
0
1
1
1
1
0
1
1
1
n+1
n
1
1
0
0
1
n+1
n
1
0
Total step count = 2n+3

Asymptotic Notations
• Asymptotic Notations are the terminology,
used to make meaningful statements about
Performance Analysis of an algorithm. (i.e.
calculating the time & space complexity)
• Different Asymptotic notations used for
Performance Analysis are –
– Big ‘Oh’ notation (O)
– Omega notation ( Ω)
– Theta notation (Θ)

Big ‘Oh’ notation (O)
• Used in Computer Science to describe the
performance or complexity of an algorithm.
• Describes the worst-case scenario, and can be
used to describe the maximum execution time
(asymptotic upper bounds) required or the
space used (e.g. in memory or on disk) by an
algorithm.

Definition:
The function f (n) = O(g(n)) ( read as ‘f of n is
said to be big oh of g of n’) if and only if there
exists a real, positive constant C and a positive
integer n0 such that,
f (n) ≤ C*g(n) for all n≥n0
Where, n is number of inputs, g(n) is function of
the size of the input data, and f(n) is the
computing time of some algorithm.

Examples – (‘=’ symbol readed as ‘is’ instead of ‘equal’)
• The function 3n+2 = O(n) as 3n+2 ≤ 4n for all n≥2
• The function 10n2
+4n+2 = O(n2
) as 10n2
+4n+2 ≤ 11n2
for all n≥5
+100n-6 = O(n2
) as 1000n2
+100n-6 ≤
1001n2
for all n≥100
• The function 6*2n
+n2
= O(2n
) as 6*2n
+n2
≤ 7*2n
for all n≥4
• The function 3n+3 = O(n2
) as 3n+3 ≤ 3n2
for all n≥2

• Consider the job offers from two companies. The first
company offer contract that will double the salary every
year. The second company offers you a contract that
gives a raise of Rs. 1000 per year. This scenario can be
represented with Big-O notation as –
• For first company, New salary = Salary X 2n
(where n is
total service years)
Which can be denoted with Big-O notation as O(2n
)
• For second company, New salary = Salary +1000n
(where n is total service years)
Which can be denoted with Big-O notation as O(n)

O(1)
Describes an algorithm that will always execute
in the same time (or space) regardless of the
size of the input data set i.e. a computing time
is a constant time.
int IsFirstElementNull(char String[])
{ if(strings[0] == ‘0’)
{ return 1;
}
return 0;
}

O(N): is called linear time,
Describe an algorithm whose performance will grow
linearly and in direct proportion to the size of the
input data set.
int ContainsValue(char String[], int no, char ch)
{ for( i = 0; i < no; i++)
{ if(string[i] == ch)
{ return 1;
}
}
return 0;
}

O(Nk
): (k fixed) refers to polynomial time; (if k=2, it is called
quadratic time, k=3, it is called cubic time),
• which represents an algorithm whose performance is directly
proportional to the square of the size of the input data set.
• This is common with algorithms that involve nested iterations over
the data set. Deeper nested iterations will result in O(N3
), O(N4
) etc.
bool ContainsDuplicates(String[] strings)
{ for(int i = 0; i < strings.Length; i++)
{ for(int j = 0; j < strings.Length; j++)
{ if(i == j) // Don't compare with self
continue;
if(strings[i] == strings[j])
return true;
}
return false;
}
}

O(2N
) : is called exponential time,
• Denotes an algorithm whose growth will
double with each additional element in the
input data set.
• The execution time of an O(2N
) function will
quickly become very large.

Omega notation (Ω)
• used in computer science to describe the
• specifically describes the best-case scenario,
and can be used to describe the minimum
execution time (asymptotic lower bounds)
required or the space used (e.g. in memory or
on disk) by an algorithm.

Definition:
The function f (n) = Ω(g(n)) ( read as ‘f of n is
said to be Omega of g of n’) if and only if there
exists a real, positive constant C and a positive
f (n) ≥ C*g(n) for all n≥ n0
Here, n0 must be greater than 0.

Examples –
• The function 3n+2 = Ω(n) as 3n+2 ≥ 3n for all n≥1
+4n+2 = Ω(n2
) as 10n2
+4n+2 ≥ n2
for all n≥1
• The function 6*2n
+n2
= Ω(2n
) as 6*2n
+n2
≥ 2n
for all n≥1
• The function 3n+3 = Ω(1)
+4n+2 = Ω(n)
+4n+2 = Ω(1)

Theta notation (Θ)
• Used in computer science to describe the
• Theta specifically describes the average-case
scenario, and can be used to describe the average
execution time required or the space used by an
algorithm.
• A description of a function in terms of Θ notation
usually only provides an tight bound on the growth
rate of the function.

Definition:
• The function f (n) = Θ(g(n)) ( read as ‘f of n is
said to be Theta of g of n’) if and only if there
exists a positive constants C1, C2, and a positive
C1*g(n) ≤ f (n) ≤ C2*g(n) for all n≥n0

Examples –
• The function 3n+2 = Θ(n) as
3n+2 ≥ 3n for all n≥2 and
3n+2 ≤4n for all n≥2
So, c1=3, c2=4 and n0=2.
• The function 3n+3 = Θ(n)
+4n+2 = Θ (n2
)
• The function 6 * 2n
+n2
= Θ(2n
)

Determining asymptotic complexity
• The asymptotic complexity (i.e. the complexity
in terms of O, Ω, Θ)
• can be determine by first determine the
asymptotic complexity of each statement in
the algorithm and then adding these
complexities one can determine asymptotic
complexity of an algorithm.

Example -1: Calculate Asymptotic complexity of
Algorithm to calculate sum of array element A of size n
Algorithm Sum(a,n)
{ s:=0;
for i:=1 to n do
s:=s+a[i];
return s;
}
Asymptotic complexity of Algorithm Sum
Statement
s/e Frequency Total steps
Algorithm Sum(a,n)
{
s:=0;
for i:=1 to n do
s:=s+a[i];
return s;
}
0
0
1
1
1
1
0
1
1
1
n+1
n
1
1
Θ(0)
Θ(0)
Θ(1)
Θ(n)
Θ(n)
Θ(1)
Θ(0)
Total Asymptotic
complexity =
=Θ(2n+2)
= Θ(n)

Practical Complexity:
• The time complexity of an algorithm is generally some
functions that depend upon instance characteristics.
• This function is very useful in determining how the time
requirements vary as the instance characteristics changes.
• The complexity function also used to compare two algorithms
that performs same task.
• Let us suppose P & Q are two algorithms used to perform
same task. Algorithm P has complexity Θ(n) and algorithm Q
has complexity Θ(n2
). Here one can declare that algorithm P is
faster than algorithm Q for sufficiently large n.

Following example shows you function values and how
various functions grows with values of n.
log n n n log n n2
n3
2n
0
1
2
3
4
5
1
2
4
8
16
32
0
2
8
24
64
160
1
4
16
64
256
1024
1
8
64
512
4096
32768
2
4
16
256
65536
4294967296

Performance Measurement:
• Is concern with obtaining the space and time
requirements of a particular algorithm. These quantities
depend on the compiler and options used as well as on
a computer on which the algorithm is run.
• To obtain computing or run time of a program we need
clocking procedures that returns the time values in
milliseconds.
• We can calculate time complexity with the help of C
programming language also. The time events are stores
in standard library (time.h) & accessed by statement
#include<time.h>.

There are two different methods for
timing events in C.
Method –I Method – II
Start timing Start=Clock(); Start=time(NULL);
Stop timing Stop=Clock(); Stop=time(NULL);
Time returned clock_t time_t
Result in
seconds
Duration=((double)(Stop –
Start)) / CLOCKS_PER_SEC
Duration=(double) difftime
(Stop, Start)

Heaps
• example of Priority queue
• supports the operations of search min or max, insert, and delete
min or max element from a queue
• Heap is viewed as a nearly complete binary tree.
• In Heap, circle represents a node and
• the value within a circle is the value stored at that node,
• the value above the node is the corresponding index at the array
and
• the lines represents relationships between two nodes.
• The node having index value 1 is called root node or parent node
and
• other nodes connected to that node are called children’s.
• In heap Parents are always to the left of their children
1
16
2
14
3
10
6
9
7
3
4
8
5
7
8
2
9
4
10
1

Heaps types
• Max heap:
A[Parent(i)] ≥ A[i]
• Min heap
A[Parent(i)] ≤ A[i]
• The main drawback of heap tree is
– extra time for creation of heap and
– too much movement of data.
– So it is not preferable for small list of data.
– For space requirement point of view it has no need
of extra space except temporary variable.

Operations on Heap: Insert
• To insert an element into the heap, one add it
‘at the bottom’ of the heap and then
compares it with its parent, grandparent,
great-grandparent, and so on, until it is less
than or equal to the one of these values.

Algorithm Insert(a,n) //Inserts a[n] into the heap which is stored at a[1: n-1]
{ i:=n;
item:=a[n];
while((i>1) and (a[(i/2)]< item)) do
{
a[i]:=a[(i/2)];
i:=[i/2];
}
a[i] :=item;
}

• Hipify the array element {100, 119, 118, 171,
112, 151, and 132) with suitable justifications
and diagrams.
• Insert three nodes having values 127,197,717
and Hapify with necessary adjustments

Sets
• Set is a collection of distinguishable objects, called as members or
elements and listed inside braces.
• If set S contain numbers as 1, 2, and 3 can be written as
S={1,2,3}.
• Two sets A and B are equal, written as A=B if they contain the
same elements e.g. {1, 2, 3} = {3, 2, 1} ={2, 1, 3} etc.
• If an object x is an member of set S, we write x S (read ‘x is∈
member of S’ or ‘x is in S’)
• If an object x is not member of set S, we write x S. If all the∉
elements of a set A are contained in a set B, then we can write A
B and read as A is subset of B.⊆
• Some special notations used in sets are –
– ∅ denotes the empty set, that is, the set containing no members.
– Z denotes a set of integers, that is, the set {…….,-2, -1, 0, 1, 2, …..}
– R denotes the set of real numbers
– N denotes the set of natural numbers, that is, the set {0, 1, 2……} (some
author starts the natural number with 1 instead of 0)

Disjoint Set
• Disjoint sets are the sets which does not have any
common elements.
• E.g. if set Si and Sj, i ≠ j, are two sets, then there exist
no elements in both Si and Sj.
• Suppose, when n=10, the elements can be partitioned
into three disjoint sets, S1={1,7,8,6}, S2={2, 5, 10} and
S3={3, 4, 9}. Possible representation of these can be
shown as –
• Each set is represented as a tree, which links the nodes
from children to the parent, rather than linking from
parent to the children
1
7 68
5
2 10
3
4 9

Operations perform on Disjoint sets: Union
• If S1 and S2 are two disjoint sets, then their
union S1 U S2 = all elements in S1 and S2, thus
S1US2= {1, 7, 8, 9, 5, 2, 10}. This can be
represented by making one of the tree as a
sub-tree of the other, as shown bellow
To obtain the union of two disjoint sets, set the
parent field as one of the roots of other root
1
7 98
5
2 10
1
7 98 5
2 10

Operations perform on Disjoint sets: Find(i)
• Given the element i, find the set containing i. Thus 7 is in set
S1, 9 is in set S3 etc.
• The searching procedure of element within a set can be
accomplished easily if we keep a pointer to the root of the
tree representing that set.
• If each root has a pointer to the set name, then to determine
which set an element is currently in we follow the parent link
to the root of its tree and use the pointer to the set name, the
data representation for set S1, S2 and S3
• can be shown as

Design and analysis of Algorithm By Dr. B. J. Mohite

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to Design and analysis of Algorithm By Dr. B. J. Mohite (20)

More from Zeal Education Society, Pune (8)

Recently uploaded (20)

Design and analysis of Algorithm By Dr. B. J. Mohite