Subject Name: Design and Analysis of

Algorithms
Module No: 1
Module Name: Introduction
 Course Objectives

1 To provide mathematical approach for Analysis of Algorithms.

To understand and solve problems using various algorithmic
2
approaches.
3 To analyze algorithms using various methods.

2 Module 1- Introduction
 What we learn in this course?
Objective 1 : To provide mathematical approach for Analysis of Algorithms.

• Recursive
• Non-Recursive
Types of Algorithm • Divide and Conquer Approach
• Greedy Method Approach
• Dynamic Programming Approach
• Backtracking and Branch and
Bound
• String Matching Algorithms
• Asymptotic analysis using Big –Oh, Omega,
Theta notations
Methods of • The substitution method
• Recursion tree method
Analysis • Master method

3 Module 1- Introduction
 What we learn in this course?
Objective 2 : To understand and solve problems using various algorithmic
approaches.

• Divide and Conquer

Approach

• Greedy Method Approach

Types of
Algorithm • Dynamic Programming
Approach

• Backtracking and Branch

and Bound

• String Matching
Algorithms

4 Module 1- Introduction
 What we learn in this course?
Objective 3 : To analyze algorithms using various methods.

• Asymptotic analysis using

Big –Oh, Omega, Theta
notations

Methods of • The substitution method

Analysis • Recursion tree method

• Master method

5 Module 1- Introduction
 Course Outcome
CO1 : Analyze the running time and space complexity of algorithms.

Describe, apply and analyze the complexity of divide and

CO2 :
conquer strategy.

CO3 : Describe, apply and analyze the complexity of greedy strategy.

Describe, apply and analyze the complexity of dynamic

CO4 :
programming strategy.

CO5 : Explain and apply backtracking, branch and bound.

CO6 : Explain and apply string matching techniques.

6 Module 1- Introduction
 Outline-Module 1
S.No Topic
Performance analysis , space and time complexity Mathematical background for
1
algorithm analysis
2 Growth of function – Big –Oh ,Omega , Theta notation

3 Analysis of Selection Sort

4 Analysis of Insertion Sort.

5 The substitution method and Recursion tree method

7 Module 1- Introduction
Module No 1: Introduction

Lecture No: 1
Performance analysis , space and
time complexity Mathematical
background for algorithm
analysis
 Algorithm

• An algorithm is a finite set of instruction that if followed accomplishes a

particular task.

Set of Rules to
obtain the
Input expected Output
output from
the given input

Algorithm

9 Module 1- Introduction
 Google Hangout Video Conference call

Algorithm??m

•How does Google Hangouts transmit live video across the

Internet so quickly?

10 Module 1- Introduction
 Google Hangout Video Conference call

Audio and Video Compression Algorithm

11 Module 1- Introduction
 How does Google Maps figure out how to get from
one place to another?
Google Map

Algorithm??
12 Module 1- Introduction
 Google Map

Route finding Algorithm

13 Module 1- Introduction
 Activity

What makes a good

algorithms?
A. Correctness
B. Efficiency

14 Module 1- Introduction
 Example: Delivery Truck

1Truck
25 location
=24! Routes
=620,448,401,
733,239,439,
360,000 routes

15 Module 1- Introduction
 Example: Delivery Truck

1Truck
25 location
..solved using
“Nearest
insertion”
algorithm

16 Module 1- Introduction
 Characteristics of an Algorithm

Well Defined Inputs

Clear and Unambiguous

Feasible

Finiteness

Language Independent

Well Defined Outputs

17 Module 1- Introduction
 Activity

Why do we need to analyze

algorithms?

18 Module 1- Introduction
 Need of Analyzing Algorithm

• To measure the performance

• Comparison of different algorithms
• Can we find a better one? Is this the best solution?
• Running time analysis
• Memory usage

19 Module 1- Introduction
Introduction to analysis of Algorithms

Analysis of Algorithms
To analyze an algorithm means determining the amount of
resources (such as time and storage) needed to execute it
•Efficiency of an algorithm can be measured in terms of:
Execution time (time complexity)
Time complexity: A measure of the amount of time required to
execute an algorithm
The amount of memory required (space complexity)
Calculated by considering data and their size

20 Module 1- Introduction
 Space complexity

How we measure Space

Complexity?

21 Module 1- Introduction
Space Complexity

 Fixed Space Requirements (C)

Independent of the characteristics of the inputs and outputs
instruction space
space for simple variables, fixed-size structured variable, constants
 Variable Space Requirements (SP(I))
depend on the instance characteristic I
number, size, values of inputs and outputs associated with I
recursive stack space, formal parameters, local variables, return address

S(P)=C+SP(I)

22 Module 1- Introduction
Example

Algorithm ADD(x,n)
{
//Problem Description: The algorithm performs addition of all the elements in an
array. Array is of floating type
//Input: An array x and n is total number of element in array
// output: return sum which is of data type float.
Sum=0.0 ----------1 unit of space by Sum
for i=1 to n do ----------1 unit of space by i ----------1 unit of space by n
Sum=Sum + x[i] ----------n unit of space by x[]
return Sum
}
S(p)≥(n+3)

23 Module 1- Introduction
 Time complexity

How we measure Time

Complexity?

24 Module 1- Introduction
 Example: Delivery Truck

Let Suppose
1.Python
Intel Dual core
6GB RAM
TIME=20MIN

2.Python
Intel Quad Core
16GB RAM
TIME=7MIN

25 Module 1- Introduction
 Example: Delivery Truck

Nearest
Number of Brute force
Insertion
nodes
1 1 1
2 4 1
3 9 2
4 16 6
…
620,448,401,
25 625 733,239,439,
360,000

n n^2 n!

26 Module 1- Introduction
Time Complexity T(P)=C+TP(I)

 Compile time (C)

independent of instance characteristics
 run (execution) time TP
Definition
A program step is a syntactically or semantically meaningful program segment
whose execution time is independent of the instance characteristics.

TP(n)=caADD(n)+csSUB(n)+cmMUL(n)+cdDIV(n)…..

Where,
n is the instance characteristics
Ca, Cm,Cs,Cd are the time for addition, multiplication,substraction,
division so on..

27 Module 1- Introduction
 Lets suppose system take
• 1 unit time for arithmetic and logical operations
Example
• 1 unit time for assignment and return statements
1.Sum of 2 numbers :
Sum(a,b)
{
return a+b
//Takes 2 unit of time(constant) one for arithmetic operation and one for
Tsum= 2 (proportional to constant)
return. cost=2 no of times=1
}
2.Sum of all elements of a list :
list_Sum(A,n)
{ //A->array and n->number of elements in the array
total =0
// cost=1 no of times=1 Tsum=1 + 2 * (n+1) + 2 * n
for i=0 to n-1 + 1 = 4n + 1 =C1 * n + C2
// cost=2 no of times=n+1 (+1 for the end false condition) (proportional to n)
sum = sum + A[i]
// cost=2 no of times=n
return sum
// cost=1 no of times=1
}
28 Module 1- Introduction
Module No 1: Introduction

Lecture No:2
Growth of function – Big Oh
,Omega , Theta notation
Asymptotic Notation( Growth of function)

 The efficiency can be measured by computing time complexity of each

algorithm
 Asymptotic notation is a shorthand way to represent the time complexity.
 It is also defines in terms of function

 Various notation such as Ω,Θ, and Ο used as asymptotic notation.

30 Module 1- Introduction
Big-oh(O) Notation [study material]

 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.
 It represent the upper
bound of algorithm
running time.

31 Module 1- Introduction
Omega Notation (Ω) [study material]

 For a given function g(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.
 It represent the lower bound of
algorithm running time

32 Module 1- Introduction
Theta Notation (Θ) [study material]

 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  c1g (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 c2g(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)≤ c2 g(n) for large enough n.
 It represent running time between
upper bound and lower bound of
algorithm.

33 Module 1- Introduction
 Lets suppose system take
• 1 unit time for arithmetic and logical operations
Example
• 1 unit time for assignment and return statements

1.Sum of 2 numbers :
Sum(a,b){
return a+b //Takes 2 unit of time(constant) one for arithmetic operation and one for
return. cost=2 no of times=1
}
Tsum= 2 = C =O(1)
2.Sum of all elements of a list :
list_Sum(A,n)
{ //A->array and n->number of elements in the array
total =0 // cost=1 no of times=1
for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition)
sum = sum + A[i] // cost=2 no of times=n
return sum // cost=1 no of times=1
}
Tsum=1 + 2 * (n+1) + 2 * n + 1 = 4n + 1 =C1 * n + C2 = O(n)

34 Module 1- Introduction
Best case, Worst case and Average case Analyses

 The worst case

 running time T(n) of an algorithm is the function defined by the
maximum number of steps taken on any instance of size n.
 The best case
 running time T(n) of an algorithm is the function defined by the
minimum number of steps taken on any instance of size n.
 The average-case
 running time T(n) of an algorithm is the function defined by an
average number of steps taken on any instance of size n.

18 Module 1- Introduction
Best, Worst, and Average Case

36 Module 1- Introduction
Order of growth

 Measuring the performance of an algorithm in relation with input size n is

called order of growth.

37 Module 1- Introduction
Order of growth

38 Module 1- Introduction
 Activity

Find the Complexity Quiz

Open Link www.kahoot.it

39 Module 1- Introduction
Answer

1. 3n+2=O(n)

2. 5n5 +100n+6=O(n5)

3. 10n2+4n+2=O(n2)

4. 2n2log(n)+ 5nlog2(n) =O(n2log(n))

5. log(log(n))+log(n) =O(log(n))

Order to follow: log(log(n), log(n), (log(n))2,

n1/3,n1/2,n,nlog(n), n2/log(n), n2, n3, 2n

40 Module 1- Introduction
Example

Consider the following algorithm

Algorithm Seq_search ( x[0,1,….n-1] ,key)

{
//problem description: This algorithm is for searching the key element from an
//array x[0,1,….n-1] sequentially
//Input: an array X[0…n-1] and search key
//output:return the index of x where key value is present.
for i-0 to n-1 do
if(x[i]==key) then
return i
}

41 Module 1- Introduction
 Activity

What is the Best Case

Complexity?

42 Module 1- Introduction
 Best case

if key element is present at first location in the list

x[0,1,….n-1] the algorithm run for a very short time
and there by we will get the best case time
complexity.
Cbest =1=O(1)

43 Module 1- Introduction
 Activity

What is the Worst Case

Complexity?

44 Module 1- Introduction
 Worst case

if key is not present in the array

Cworst =n+1=O(n)

45 Module 1- Introduction
 Activity

What is the Average Case

Complexity?

46 Module 1- Introduction
Average Case

Let the algorithm is for sequential search and P be a probability of getting

successful search n is the total number of elements in the list.
• The first match of the element will occur at ith location. Hence
probability of occurring first match is P\n for every ith element.
• The probability of getting unsuccessful search is(1-P)
Now we can find average case
Cavg(n)=Probability of successful search + Probability of unsuccessful
search
Cavg=[1.P/n+2. P/n+3. P/n……+i. P/n]+n(1-P)
=P/n [1+2+3……i+….n]+n(1-P)
=P(n+1)/2 + n(1-P)
If P=0 means no successful search
Cavg=n --> worst case
If P=1 we get a successful search
Cavg=(n+1)/2

47 Module 1- Introduction
Module No 1: Introduction

Lecture No:3
Analysis of Selection Sort
Selection Sort

Idea:
Find the smallest element in the array
Exchange it with the element in the first position
Find the second smallest element and exchange it with the element in the
second position
Continue until the array is sorted
Disadvantage:
Running time depends only slightly on the amount of order in the file

49
Module 1- Introduction
Example

8 4 6 9 2 3 1 1 2 3 4 9 6 8

1 4 6 9 2 3 8 1 2 3 4 6 9 8

1 2 6 9 4 3 8 1 2 3 4 6 8 9

1 2 3 9 4 6 8 1 2 3 4 6 8 9

50
Module 1- Introduction
Selection Sort

Algorithm SELECTION-SORT(A[0,1….n-1])
{//problem description: This algorithm sort the element using selection sort
//Input: an array of element a[0,1…n-1] that is to be stored
//output: the sorted array A[0,1,….n-1]
for i ← 0 to n – 2
do smallest ← i 8 4 6 9 2 3 1
for j ← i + 1 to n-1
do if A[j] < A[smallest]
then smallest ← j
//swap A [i] and A[smallest]
temp=A[i]
A[i]=A[smallest]
A[smallest]=temp
}

51
Module 1- Introduction
 Analysis of Selection Sort
SELECTION-SORT(A[0,1….n-1]) cost times
for i ← 0 to n – 2 c1 n
do smallest ← I c2 n-1
 (n  i )
n2
for j ← i + 1 to n-1 c3
i 0

 (n  i  1)
n2
do if A[j] < A[smallest] c4 i 0


n2
then smallest ← j c5 i 0
(n  i  1)
//swap A [i] and A[smallest]
temp=A[i] c6 n-1
A[i]=A[smallest] c7 n-1
A[smallest]=temp c8 n-1

T(n)= c1n+ c2 (n-1) + c3 i 0 (n  i ) + (c4 +c5 ) i 0 ( n  i  1)+(c6 +c7 +c8 )n-1

n2 n2

=O(n²)

52 52
Module 1- Introduction
Analysis of Selection Sort

Step 1: the Input size is n

Step 2: Basic Operation : if A[j]<A[smallest]
Step 3:The comparison is executed on each repletion of the loop

n2
c(n)= ( n  i  1)
i 0

Step 4: Calculation of complexity


n2
c(n)=
i 0
( n  i  1)
( n  1)i  0 1 i  0 i
n2 n2
=

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

= n(n-1)/2

=O(n²)

53
Module 1- Introduction
 Activity

What is the Best and Worst

Case Complexity?

54 Module 1- Introduction
Thank You