CSE 2105: Data Structures and Algorithms
Algorithm and
Complexity
Analysis
Md Mehrab Hossain Opi
Algorithm 2
An algorithm is a step-by-step procedure for solving
a problem in a finite amount of time.
CSE 2105: Data Structures and Algorithms 08/15/2025
Performance Analysis of Algorithm 3
Program Performance is the amount of computer
memory and time needed to run a program.
CSE 2105: Data Structures and Algorithms 08/15/2025
Criteria for Measurement 4
• Two criteria are used to judge algorithms
• Time Complexity
• Space Complexity
• Space Complexity of an algorithm is the amount of memory it needs
to run to completion.
• Time Complexity of an algorithm is the amount of CPU time it needs
to run to completion.
• Analysis of running time generally has received more attention than
memory.
CSE 2105: Data Structures and Algorithms 08/15/2025
Time Complexity 5
• It is often difficult to get reliable timing figures because of clock
limitations and a multi-programming or time-sharing environment.
• The exact time we determine would not apply to many machines.
• We will concentrate on developing only the frequency count for all
statements.
CSE 2105: Data Structures and Algorithms 08/15/2025
Time Complexity 6
Consider the following code snippets
1. Frequency count is 1.
Frequency count is .
2.
Frequency count is n.
}
Frequency count is .
3.
Frequency count is .
Frequency count is
}
}
CSE 2105: Data Structures and Algorithms 08/15/2025
Types of Time Complexities 7
• Time Complexity usually depends on the size of the algorithm and
input.
• The best-case time complexity of an algorithm is a measure of the
minimum time that the algorithm will require for an input of size n.
• The worst-case time complexity of an algorithm is a measure of the
maximum time that the algorithm will require for an input of size n.
• After knowing the worst-case time complexity, we can guarantee that
the algorithm will never take more than this time.
CSE 2105: Data Structures and Algorithms 08/15/2025
Types of Time Complexities 8
• The time that an algorithm will require to execute a typical input data
of size n is known as average-case time complexity.
• We can say that the value obtained by averaging the running time of
an algorithm for all possible inputs of size n can determine average
case time complexity.
CSE 2105: Data Structures and Algorithms 08/15/2025
Types of Time Complexities 9
• Consider the following code snippets
• What will be the time complexity of this function?
CSE 2105: Data Structures and Algorithms 08/15/2025
Types of Time Complexities 10
• Best-Case Time Complexity
• If the first item of the array is our desired value the loop will run only once.
• Total run time = 5
• How?
• Worst-Case Time Complexity
• If the desired value does not exist in the array loop will run n+1 time.
• Total run time = 1 + (n+1) + (n) + (n) + 1 = 3n+3
• Can you find out the average case time complexity?
CSE 2105: Data Structures and Algorithms 08/15/2025
O(Big-Oh) Notation 11
• We will represent the worst-case complexity using Big-Oh notation.
• You will learn more about asymptotic notation in the next semester.
• Suppose the complexity of any program is . Then using Big-Oh notation
we will write it .
CSE 2105: Data Structures and Algorithms 08/15/2025
O(Big-Oh) Notation 12
• When using Big-Oh notation, we will discard the following
• Lower-Order Terms
• Lower-order terms become negligible as n grows.
• If the actual complexity is we simply write
• Constant Factors
• If the complexity is we write
• If the complexity of an algorithm is we can simply write
CSE 2105: Data Structures and Algorithms 08/15/2025
Rules of Complexity Analysis - Sequence 13
• The worst-case running time of a sequence of m statements such as
is The running time of statement in the sequence is .
CSE 2105: Data Structures and Algorithms 08/15/2025
Rules of Complexity Analysis - Iteration 14
• The worst-case running time of a C for loop
is . is the number of iterations executed in the worst case.
CSE 2105: Data Structures and Algorithms 08/15/2025
Rules of Complexity Analysis - Selection 15
• The worst-case running time of a C if-else
is .
CSE 2105: Data Structures and Algorithms 08/15/2025
Examples 16
CSE 2105: Data Structures and Algorithms 08/15/2025
Examples 17
CSE 2105: Data Structures and Algorithms 08/15/2025
Examples 18
CSE 2105: Data Structures and Algorithms 08/15/2025
Examples 19
• What will be the complexity of the following function?
void function(int n)
{
int i = 1, s = 1;
while (s < n) {
s = s + i;
i++;
}
}
Time complexity: root(n)
CSE 2105: Data Structures and Algorithms 08/15/2025
Example 20
• What is the time complexity of the following code?
void fun(int n)
{
if (n < 5)
printf(“Hello");
else {
for (int i = 0; i < n; i++) {
printf("%d", i);
}
}
}
CSE 2105: Data Structures and Algorithms 08/15/2025
Example 21
• Can you say the time complexity of binary search now?
CSE 2105: Data Structures and Algorithms 08/15/2025
References 22
• Miscellaneous Problems of Time Complexity – GeeksforGeeks
• Time Complexity: Key Problems & Solutions | by Vishad Patel | Medium
• PPT - SPACE COMPLEXITY & TIME COMPLEXITY PowerPoint Presentation
- ID:6485906
• Time and Space Complexity | PPT
CSE 2105: Data Structures and Algorithms 08/15/2025
CSE 2105: Data Structures and Algorithms 08/15/2025 23
Thank You.
