CS378: Design and Analysis of Algorithms
Algorithm Analysis
Frequency/Step Count Method
Mr. Salman Ashraf
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Iterative vs Recursive Algorithm
Iterative Algorithm Recursive Algorithm
• Uses loops (for, while, do-while) • A function calls itself.
• Repeats instructions until a condition is • Must have:
met. – Base case (to stop recursion)
– Recursive case (problem broken
into smaller subproblems)
Example: finding sum of first n numbers. Example: finding sum of first n numbers.
def sum_iterative(n): def sum_recursive(n):
total = 0 if n == 0:
for i in range(1, n+1): return 0
total += i return n + sum_recursive(n-1)
return total
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: 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(n2)
5. Cubic time – O(n3)
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
CS378: Design and Analysis of Algorithms
What is Step Count Method?
Time complexity can be calculated by using the following two
types of methods:
• 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) time.
• for(i = 0; i < n ; i++), is a loop and it takes O(n+1) time.
• if(arr[i] == key), is a conditional statement and takes O(n) time.
• printf(“Found”), is a function and that takes O(1) time.
• Therefore, the total number of times it is executed is 2n+3. As we ignore
lower exponents in time complexity, total time becomes O(n).
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: 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(n2)
Space Complexity = O(n2)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Examples
Algorithm MatrixMultiplication (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);
}
}
}
Running Time Complexity = O(n3)
return 0; Space Complexity = O(n2)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Examples
for(i = 0; i < n; i++) { for(i = 1; i < n; i = i * 2) {
for(j = 0; j < i; j++) { operation;
}
operation;
}
for(i = n; i >= 1; i = i / 2) {
} operation;
}
p = 0;
for(i = 1; p <= n; i++) { for(i = 1; i * i < n; i++) {
p = p + i; operation;
} }
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Examples
p=0 for(i = 0; i < n; i++)
for(i = 1; i < n; i = i * 2) {
{ for(j = 0; j < n; j = j * 2)
{
p++;
operation;
} }
for(j = 1; j < p; j = j * 2) }
{
opertaion;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi