The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes.

Distribution and modifications of the content is prohibited.

Module 4:

Algorithm Analysis
CO4: analyze the performance of algorithms using asymptotic analysis and apply various
design techniques to solve a given problem.

Subject In-charge
Mrs. Sonali Suryawanshi
Assistant Professor
Class : III SEM SEIT-A & B
email: sonalisuryawanshi@[Link]

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 1
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 4:

Algorithm Analysis

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 2
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.1 - ALGORITHM COMPLEXITY

Suppose X is an algorithm and n is the size of input data, the time and space
used by the algorithm X are the two main factors, which decide the
efficiency of X.

Time Factor − Time is measured by counting the number of key operations

such as comparisons in the sorting algorithm. Complexity of an algorithm
f(n) gives the running time.

Space Factor − Space is measured by counting the maximum memory space

required by the algorithm.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 3
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Space Complexity: represents the amount of memory space required

by the algorithm in its life cycle.

the sum of two components −

A fixed part to store certain data and variables, that are independent
of the size of the problem.
For example, simple variables and constants used, program size, etc.

A variable part by variables, whose size depends on the size of the

problem. For example, dynamic memory allocation, recursion stack
space, etc.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 4
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Space Complexity: represents the amount of memory space

required by the algorithm in its life cycle.

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

three variables A, B, and C and one constant.

Hence S(P) = 1 + 3.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 5
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Time Complexity : represents the amount of time required by

the algorithm to run to completion.

Time requirements can be defined as a numerical function T(n),

where T(n) can be measured as the number of steps, provided
each step consumes constant time.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 6
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

ALGORITHM ANALYSIS
Efficiency of an algorithm can be analyzed at two different
stages, before implementation and after implementation. They
are the following –

● A Priori Analysis or Performance or Asymptotic Analysis

● A Posterior Analysis or Performance Measurement

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 7
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

A Priori Analysis or Performance or Asymptotic Analysis

● Theoretical analysis of an algorithm.

● Assuming that all other factors, for example, processor speed,
are constant and have no effect on the implementation.
● to estimate the complexity in the asymptotic sense, i.e., to
estimate the complexity function for arbitrarily large input.
Big-O notation, Omega notation, and Theta notation are used to
estimate the complexity function for large arbitrary input.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 8
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

A Posterior Analysis or Performance Measurement −

● This is an empirical analysis of an algorithm.

● The selected algorithm is implemented using programming
language.
● This is then executed on target computer machine.
● In this analysis, actual statistics like running time and space
required, are collected.
●
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 9
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

● Types of Analysis
Best Case Analysis : least amount of time to execute a
specific set of input,

Average Case Analysis : time complexity of an algorithm for

certain sets of inputs are on an average,

Worst Case Analysis: algorithm takes maximum amount of

time to execute for a specific set of input,

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 10
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.2 : MATHEMATICAL NOTATION : Asymptotic Notations

notations such as O (Big-O), Ώ (Omega), and θ (Theta) are

called as asymptotic notations.

used in three different cases of time complexity.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 11
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Order of Growth
○ Describes how performance (time/space) increases as input
size grows.
○ Expressed using asymptotic notations:

■ Big-O (worst case)

■ Big-Ω (omega )(best case)

■ Big-Θ (theta) (average/tight bound).

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 12
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 13
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 14
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Big O(order of) Notation

▪ It provides the upper bound for the complexity.

▪ Concerned with what happens for very large values of n.
▪ Example: if a sorting algorithm performs n^2 operations to sort
just n elements, then that algorithm would be described as an
O(n^2) algorithm.
▪ In this, constant multipliers are ignored.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 15
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Big O Notation

▪ Big O notation is simply written as:

f(n) ∈ O(g(n)) or f(n) = O(g(n))

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 16
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Consider function f(n) = 2(n)+2 and g(n) = n^2.

We need to find the constant c such that f(n) ≤ c ∗
g(n).
Let n = 1, then
f(n) = 2(n)+2 = 2(1)+2 = 4
g(n) = n^2 = 1^2 = 1
Here, f(n)>g(n)
Let n = 2, then
f(n) = 2(n)+2 = 2(2)+2 = 6
g(n) = n^2 = 2^2 = 4
Here, f(n)>g(n)
Let n = 3, then
f(n) = 2(n)+2 = 2(3)+2 = 8
g(n) = n^2 = 3^2 = 9
Here, f(n)<g(n)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 17
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Consider function f(n) = 2(n)+2 and g(n) = n^2.

Thus, when n is greater than 2, we get
We need to find the constant c such that f(n) ≤ c ∗ g(n).
f(n)<g(n). In other words, as n
Let n = 1, then
becomes larger,
f(n) = 2(n)+2 = 2(1)+2 = 4
the running time increases
g(n) = n^2 = 1^2 = 1
considerably. This concludes that the
Here, f(n)>g(n)
Big-O helps to
Let n = 2, then
determine the ‘upper bound’ of the
f(n) = 2(n)+2 = 2(2)+2 = 6
algorithm’s run-time.
g(n) = n^2 = 2^2 = 4
Here, f(n)>g(n)
Let n = 3, then
f(n) = 2(n)+2 = 2(3)+2 = 8
g(n) = n^2 = 3^2 = 9
Here, f(n)<g(n)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 18
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Limitations of Big O Notation

1. Many algorithms are simply too hard to analyse mathematically.
2. There may not be sufficient information to calculate the behaviour
of the algorithm in the average case.
3. Big O analysis only tells us how the algorithm grows with the size of
the problem,not how efficient it is, as it does not consider the
programming effort.
4. It ignores important constants. For example, if one algorithm takes
O(n^2 ) time to execute and the other takes O(100000n^2 ) time to
execute, then as per Big O, both algorithm have equal time
complexity. In real-time systems, this may be a serious
consideration.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 19
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

‘Ω’ - Omega notation.

● Omega describes the manner in which an algorithm performs in the

best case time complexity.

● omega gives the "lower bound" of the algorithm's run-time.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 20
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

‘Ω’ - Omega notation.

f(n) ≥ c ∗ g(n)

Where, n is any number of inputs or outputs and f(n) and g(n) are two
non-negative functions.

These functions are true only if there is a constant c and a non-negative

integer n0 such that n>n0.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 21
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

‘Ω’ - Omega notation. f f(n) is bounded below by some

constant multiple of g(n) for all
large values of n, i.e., if there
exists some positive constant c
and some non-negative integer
n0, such that f(n) ≥ c ∗ g(n) for all
n ≥n0.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 22
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Consider function f(n) = 2n^2+5 and g(n) = 7n.

‘Ω’ - Omega notation. We need to find the constant c such that f(n) ≥ c ∗
g(n).
Let n = 0, then
f(n) = 2n^2+5 = 2(0)^2+5 = 5
g(n) = 7(n) = 7(0) = 0
Here, f(n)>g(n)

Let n = 1, then
f(n) = 2n^2+5 = 2(1)^2+5 = 7
g(n) = 7(n) = 7(1) = 7
Here, f(n)=g(n)

Let n = 2, then
f(n) = 2n^2+5 = 2(2)^2+5 = 13
g(n) = 7(n) = 7(2) = 14
Here, f(n)<g(n)
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 23
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Consider function f(n) = 2n^2+5 and g(n) = 7n.

‘Ω’ - Omega notation. We need to find the constant c such that f(n) ≥ c ∗
g(n).
Let n = 0, then
f(n) = 2n^2+5 = 2(0)^2+5 = 5
g(n) = 7(n) = 7(0) = 0
Here, f(n)>g(n)
Thus, for n=1, we get f(n) ≥ c ∗ g(n).
Let n = 1, then
This concludes that Omega helps to f(n) = 2n^2+5 = 2(1)^2+5 = 7
determine the "lower bound" of the algorithm's
g(n) = 7(n) = 7(1) = 7
run-time.
Here, f(n)=g(n)

Let n = 2, then
f(n) = 2n^2+5 = 2(2)^2+5 = 13
g(n) = 7(n) = 7(2) = 14
Here, f(n)<g(n)
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 24
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Theta Notation - 'θ'

Theta notation is used when the upper bound and lower bound of an
algorithm are in the same order of Magnitude.

Theta can be defined as:

c1 ∗ g(n) ≤ f(n) ≤ c2 ∗ g(n) for all n>n0

Where, n is any number of inputs or outputs and f(n) and g(n) are two non-
negative functions. These functions are true only if there are two constants
namely, c1, c2, and a non-negative integer n0.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 25
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Theta Notation - 'θ'

Theta can also be denoted as f(n) = θ(g(n)) where, f of n is equal to Theta of g

of n. The graphical representation of f(n) = θ(g(n))

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 26
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Theta Notation - 'θ'

Consider function f(n) = 4n + 3 and g(n) = 4n for all n ≥ 3; and f(n) = 4n + 3

and g(n) = 5n for all n ≥ 3.

Then the result of the function will be:

Let n = 3
f(n) = 4n + 3 = 4(3)+3 = 15
g(n) = 4n =4(3) = 12 and

f(n) = 4n + 3 = 4(3)+3 = 15
g(n) = 5n =5(3) = 15 and

here, c1 is 4, c2 is 5 and n0 is 3
Thus, from the above equation we get c1*g(n) < f(n)< c2 *g(n). This concludes that Theta
notation depicts the running time between the upper bound and lower bound.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 27
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Rules for Time Complexity Calculation

1. Single Statement 2. Loop

c = a+b for i←1 to n → n times

s←s+a[i] → n.1 times
T(n) = O(1)
T(n)= n+n(1)

= 2n

∴ T(n)= O(n)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 28
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Rules for Time Complexity Calculation

3. Nested for
for i←1 to n
for j← 1 to n
s ←s+a[i]

T(n)= n+n^2+n^2

∴ T(n)= O(n^2)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 29
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.4 ALGORITHM DESIGN TECHNIQUE

[Link] and Conquer
2 Back Tracking Method
3 Dynamic programming

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 30
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

[Link] and Conquer :

Divide and Conquer approach basically

works on breaking the problem into
subproblems that are similar to the
original problem but smaller in size &
simpler to solve.

Once divided sub problems are solved

recursively and then combine solutions of
sub problems to create a solution to
original problem.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 31
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

[Link] and Conquer :

At each level of the recursion the divide and conquer approach follows three
steps:
Divide: In this step whole problem is divided into several sub problems.

Conquer: The sub problems are conquered by solving them recursively, only if
they are small enough to be solved, otherwise step 1 is executed.

Combine: In this final step, the solution obtained by the sub problems are
combined to create solution to the original problem.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 32
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 33
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Examples: The specific computer algorithms are based on the Divide &
Conquer approach:

1. Maximum and Minimum Problem

2. Binary Search
3. Sorting (merge sort, quick sort)
4. Tower of Hanoi.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 34
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Disadvantages of Divide and Conquer

● Since most of its algorithms are designed by incorporating

recursion, so it necessitates high memory management.

● An explicit stack may overuse the space.

● It may even crash the system if the recursion is performed

rigorously greater than the stack present in the CPU.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 35
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

2. Backtracking

● uses a recursive approach to explain the problems.

● We can say that the backtracking is needed to find all

possible combination to solve an optimization problem

● Backtracking is a systematic way of trying out

different sequences of decisions until we find one that
"works."
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 36
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

2. Backtracking

● Backtracking can understand of as searching a tree for a

particular "goal" leaf node.

To "explore" node N:
1. If N is a goal node, return "success"
2. If N is a leaf node, return "failure"
3. For each child C of N, Explore C
If C was successful, return "success"
4. Return "failure"

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 37
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

3. Greedy Algorithms

make locally optimal choices at each step with the hope of finding a global optimum solution.

● At every step of the algorithm, we make a choice that looks the best at the moment. To make the
choice, we sometimes sort the array so that we can always get the next optimal choice quickly. We
sometimes also use a priority queue to get the next optimal item.
● After making a choice, we check for constraints (if there are any) and keep picking until we find the
solution.
● Greedy algorithms do not always give the best solution.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 38
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

3. Greedy Algorithms

● Greedy algorithm examples are: Dijkstra's Algorithm Prim and Kruskal's

Algorithm Huffman Coding Tree.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 39
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4. Dynamic programming

● is similar to divide-and-conquer technique.

● Both techniques solve a problem by breaking it down into several

sub-problems that can be solved recursively.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 40
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4. Dynamic programming vs Divide and conquer

● Divide & Conquer approach partitions the problems into independent

sub-problems, solve the sub-problems recursively, and then combine
their solutions to solve the original problems.

● Whereas dynamic programming is applicable when the sub-problems

are not independent, that is, when subproblems share sub subproblems

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 41
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4. Dynamic programming vs Greedy

● As Greedy approach, Dynamic programming is typically applied to

optimization problems and for them there can be many possible
solutions and the requirement is to find the optimal solution among
those.
● In greedy solutions are computed by making choices in serial
forward way and in this no backtracking & revision of choices is done
● Dynamic programming computes its solution bottom up by
producing them from smaller sub problems, and by trying many
possibilities and choices before it arrives at the optimal set of
choices.
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 42
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4. Dynamic programming vs Greedy

Various algorithms which make use of Dynamic programming technique

are as follows:
● 1. Knapsack problem.
● 2. Chain matrix multiplication.
● 3. All pair shortest path.
● 4. Travelling salesman problem.
● 5. Tower of hanoi.
● 6. Checker Board.
● 7. Fibonacci Sequence.
● 8. Assembly line scheduling.
● [Link]
Optimal binary
Technology search trees.
St. Francis Institute of Technology Data Structures and Analysis
of Information Sonali Suryawanshi 43
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.3 : Recurrence relations

A recurrence relation is a mathematical expression that defines a

sequence in terms of its previous terms. In the context of algorithmic
analysis, it is often used to model the time complexity of recursive
algorithms.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 44
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

How to calculate time complexity:

Q. Imagine a classroom of 100 students in which you gave your pen to one person. You have to find that pen
without knowing to whom you gave it.
Here are some ways to find the pen and what the O order is.
● O(n2): You go and ask the first person in the class if he has the pen. Also, you ask this person about the
other 99 people in the classroom if they have that pen and so on,
This is what we call O(n2).
● O(n): Going and asking each student individually is O(N).
● O(log n): Now I divide the class into two groups, then ask: "Is it on the left side, or the right side of the
classroom?" Then I take that group and divide it into two and ask again, and so on. Repeat the process
till you are left with one student who has your pen. This is what you mean by O(log n).
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 45
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

How to calculate time complexity:

I might need to do:
● The O(n2) searches if only one student knows on which student the pen is hidden.
● The O(n) if one student had the pen and only they knew it.
● The O(log n) search if all the students knew, but would only tell me if I guessed the right side.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 46
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Please note time complexity is not running time of algorithm

Write code in C/C++ or any other language to find the maximum between N numbers, where N varies
from 10, 100, 1000, and 10000. For Linux based operating system (Fedora or Ubuntu), use the below
commands:
To compile the program: gcc program.c – o program
To execute the program: time ./program

You will get surprising results i.e.:

● For N = 10: you may get 0.5 ms time,
● For N = 10,000: you may get 0.2 ms time.
● Also, you will get different timings on different machines. Even if you will not get the same
timings on the same machine for the same code, the reason behind that is the current network
load.

So, we can say that the actual time required to execute code is machine-dependent
St. Francis Institute of Technology
(whether
Data Structures you are
and Analysis
Department of Information Technology Sonali Suryawanshi 47
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Time Complexity: In the above

#include <iostream>
code “Hello World” is printed
int main() only once on the screen.
{ So, the time complexity is
cout << "Hello World"; constant: O(1) i.e. every time a
return 0;
constant amount of time is
required to execute code, no
}
matter which operating system or
which machine configurations you
are using.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 48
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

int main()
{
Time Complexity:
int i, n = 8;
In the above code “Hello World !!!” is
for (i = 1; i <= n; i++) { printed only n times on the screen, as
cout << "Hello World !!!\n"; the value of n can change.
}
return 0; So, the time complexity is linear:
}
O(n) i.e. every time, a linear amount
of time is required to execute code.

Auxiliary Space: O(1)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 49
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

int main()
{ Time Complexity: O(log2(n))
Auxiliary Space: O(1)
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
cout << "Hello World !!!\n";
}
return 0;
}
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 50
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

int main()
{ Time Complexity: O(log(log2(n)))
Auxiliary Space: O(1)
int i, n = 8;
for (i = 2; i <= n; i=pow(i,2)) {
cout << "Hello World !!!\n";
}
return 0;
}
Hello World !!!
Hello World !!!

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 51
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

#include <iostream>
Time Complexity:
using namespace std;
● The above code will take 2 units of
int sum(int a,int b)
time(constant):
{
○ one for arithmetic operations and
return a+b;
○ one for return. (as per the above
}
conventions).
● Therefore total cost to perform sum operation
int main() {
(Tsum) = 1 + 1 = 2
int a = 5, b = 6;
● Time Complexity = O(2) = O(1), since 2 is
cout<<sum(a,b)<<endl;
constant
return 0;
}
St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 52
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

#include <iostream>
int list_Sum(int A[], int n)
{
int sum = 0; // cost=1 no of times=1
for(int i=0; i<=n-1;i++) // 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 + 4 =C1 * n + C2 =
int main() O(n)
{
int A[] = { 5, 6, 1, 2 };
int n = sizeof(A) / sizeof(A[0]);
cout << list_Sum(A, n);
return 0;
}

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 53
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

int main()
{
int n = 3;
int m = 3;
int arr[][3]
= { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } };
int sum = 0;

// Iterating over all 1-D arrays in 2-D array

for (int i = 0; i < n; i++) {

// Printing all elements in ith 1-D array

for (int j = 0; j < m; j++) {
The program iterates through all the
elements in the 2D array using two
// Printing jth element of ith row nested loops. The outer loop iterates
sum += arr[i][j]; n times and the inner loop iterates m
} times for each iteration of the outer
} loop.
cout << sum << endl; Therefore, the time complexity of
return 0; the program is O(n*m).
} St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 54
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Miscellaneous problem practice to calculate time complexity :

[Link]
/

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 55
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.3 : Recurrence relations A recurrence relation is an

equation that defines a
sequence by expressing each
term as a function of one or
more previous terms

[Link]

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 56
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Types of Recurrence
4.3 : Recurrence relations
Relations:
Various types of Recurrence
Relations are:
1. Linear Recurrence
Relations
2. Divide and Conquer
Recurrences
3. Substitution Recurrences
4. Homogeneous Recurrences
5. Non-Homogeneous
Recurrences

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 57
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.3 : Recurrence relations

1. Linear Recurrence Relations:

Following are some of the examples of recurrence relations based on linear recurrence relation.

1. T(n) = T(n-1) + n for n > 0 and T(0) = 1

These types of recurrence relations can be easily solved using substitution method.
For example,
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-k) + (n-(k-1))….. (n-1) + n

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 58
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.3 : Recurrence relations

1. Linear Recurrence Relations:

These types of recurrence relations can be easily solved using substitution method.
For example,
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-k) + (n-(k-1))….. (n-1) + n

Substituting k = n, we get

T(n)=T(0)+1+2+…..+n= n(n+1)/2 = O(n^2)

St. Francis Institute of Technology Data Structures and Analysis
Department of Information Technology Sonali Suryawanshi 59
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

4.3 : Recurrence relations

● Recursion Tree Method
● Numericals on Recursion Tree Method
● Master Method
● Numericals on Master Method
● References

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 60
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 61
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 62
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 63
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 64
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 65
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 66
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 67
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

T(n)

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 68
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 69
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 70
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 71
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 72
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 73
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 74
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

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

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 75
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Solve T(n) = 3T(n/4) + cn^2

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 76
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Solve T(n) = 3T(n/4) + cn^2

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 77
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Solve T(n) = 3T(n/4) + cn^2

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 78
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Solve T(n) = T(n/3) + T(2n/3) + cn

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 79
 The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Master Method is a direct way to get the solution. The master

method works only for the following type of recurrences or for
recurrences that can be transformed into the following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

St. Francis Institute of Technology Data Structures and Analysis

Department of Information Technology Sonali Suryawanshi 80