CS 478: Design and Analysis of Algorithms
Algorithm Analysis
Frequency/Step Count Method
Fall 2024
Mr. Ahsan Shah
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Time Complexity
• Time Complexity is the amount of time taken by the algorithm to run. It measures the
time taken to execute each statement of code in an algorithm.
• Time complexity is given by time as a function of the length of the input. And, there
exists a relation between the input data size (n) and the number of operations
performed (N) with respect to time. This relation is denoted as Order of growth in
Time complexity and given notation O[n] where O is the order of growth and n is the
length of the input.
1. Constant time – O (1)
2. Linear time – O (n)
3. Logarithmic time – O (log n)
4. Quadratic time – O (n^2)
5. Cubic time – O (n^3)
and many more complex notations like Exponential time, Quasilinear time, factorial
time, etc. are used based on the type of functions defined.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
What is Step Count Method?
Time Complexity can be calculated by using Two types of
methods. They are:
• Step Count Method
• Asymptotic Notation.
“The step count method is one of the methods to analyze
the Time complexity of an algorithm. In this method, we
count the number of times each instruction is executed.
Based on that we will calculate the Time Complexity.”
Linear Search:
• i = 0, is an initialization statement and takes O(1) times.
• for(i = 0;i < n ; i++), is a loop and it takes O(n+1) times .
• if(arr[i] == key), is a conditional statement and takes O(n) times.
• printf(“Found”), is a function and that takes O(0)/O(1) times.
• Therefore Total Number of times it is executed is 2n + 3 times. As we ignore
lower exponents in time complexity total time became O(n).
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Examples
Algorithm Sum (arr, n) Algorithm ArraySum (arr1, arr2, n)
sum=0; arr3 = {0};
for(i=0; i<n; i++) for(i=0; i<n; i++)
{ {
sum = sum + arr [i]; for(j=0; j<n; j++)
} {
Return 0; arr3(i,j) = arr1(i,j) + arr2(i,j);
Running time Complexity =O(n)
}
Space Complexity= O(n) }
Return 0;
Running time Complexity =O(n^2)
Space Complexity= O(n)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Examples
Algorithm Matrix Multiplication (arr1, arr2, n)
arr3 = {0};
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
arr3(i,j) = 0;
for(k=0; k<n; k++)
{
arr3 (i,j) = arr3(i,j)+arr1(i,k)*arr2(k,j);
}
}
}
Return 0;
Running time Complexity =O(n^3)
Space Complexity= O(n^2)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
