Performance Analysis of the Algorithm | DSA Tutorials

Performance Analysis of Algorithm – To understand how an algorithm can perform on different sizes of input, we need to analyse the algorithm in different cases. And to compute the best, average, and worst running time of an algorithm, we need to consider three cases of an algorithm.

Performance Analysis of an Algorithm

The performance analysis of an algorithm depends on two factors: Time complexity and space complexity.

1. Time Complexity – This measure is used to estimate the running time of an algorithm in terms of the size of the input data. For this purpose, a popular notation called big ‘O’ notation is used.
2. Space Complexity – This measure is used to define extra space consumed by the algorithm, except for input data. This is also measured in terms of input size, and big ‘O’ notation is also popular in this case as well.

Calculate the Time and Space Complexity of the Algorithm

To calculate the time and space complexity of an algorithm, we use Big O notation, Omega notation and Theta notation.

Big Oh notation – The function f(n) = O(g(n)) (read as “f of n is big oh of g of n”) if and only if there exist positive constants c and m such that f(n) <= c*g(n) for all n, n>= m.

Example

1. The function 3n + 2 = O(n) as 3n + 2 <= 4n for all n >= 2.
2. The function 6*2ⁿ+n2 = O(2ⁿ) as 6*2ⁿ+n² <= 7*2ⁿ for all n >= 4.

We write O(1) to mean a computing time that is a constant. O(n) is a linear, O(n²) is called quadratic, O(n³) is called cubic, and O(2ⁿ) is called exponential. If an algorithm takes time O(log N), it is faster than O(n).

Omega notation – The function f(n) = Ω(g(n)) (read as “f of n is omega of g of n”). if and only if there exist positive constants c and m such that f(n) >= c*g(n) for all n, n>=m.

Example

1. The function 3n+2 = Ω(n) as 3n+2 >= 3n for all n>=1.
2. The function 6*2ⁿ+n² = Ω(2ⁿ) as 6*2ⁿ+n² >= 6*2ⁿ for all n>=1.

Theta notation – The function f(n) = $\Theta$ (g(n)) (read as “f of n is theta of g of n”). if and only if there exist positive constants c and m such that c*g(n) <= f(n) <= c2*g(n) for all n, n>=m.

Example

1. The function 3n+2 = $\Theta$ (n) as 3n + 2 >= 3n for all n>=1 and 3n + 2 <= 4n for all n >= 2.
2. The function 6*2ⁿ + n² = $\Theta$ (2ⁿ).

Counting the number of steps of the algorithm

We can determine the number of steps needed by a program to solve a particular problem instance in one of two ways. In the first method, we introduce a new variable, count, into the program. This is the global variable with an initial value of 0. Statements to increment the count by the appropriate amount are introduced into the program. This is done so that each time a statement in the original program is executed, the count is incremented by the step count of that statement.

Algorithm Sum(a,n)
{
   S:=0
   count := count + 1 [count is global it is initially zero.]
   for i: = 1 to n do
   {
        count := count + 1 [for FOR loop]
        s := s + a[i]
        count := count + 1 [for s]
   }
   count := count + 1[for last time of for]
   count := count + 1[for the return]
   return s
}

Performance Analysis of the Algorithm Cases

Choosing the input to consider when analysing an algorithm can have a significant impact on how an algorithm will perform. For example, if the input list is already sorted, some sorting algorithms will perform very well, but other sorting algorithms may perform very poorly. The opposite may be true if the list is randomly arranged instead of sorted. Hence, multiple input sets must be considered while analysing an algorithm. These include the following:

1. Best Case Input Analysis:- This represents the input set that allows an algorithm to perform most quickly. With this input, the algorithm takes the shortest time to execute, as it causes the algorithm to do the least amount of work. For example, for a searching algorithm, the best case would be if the value we are searching for is found in the first location that the search algorithm checks. As a result, this algorithm would need only one comparison, irrespective of the complexity of the algorithm. No matter how large the input is, searching in the best case will result in a constant time of 1. Since the best case for an algorithm would usually be a very small and frequently constant value, a best-case analysis is often not done.
2. Worst Case Input Analysis:- This represents the input set that allows an algorithm to perform most slowly. Worst-case analysis is an important analysis because it gives us an idea of the worst-case scenario an algorithm will ever take. Worst-case analysis requires that we identify the input values that cause an algorithm to do the most work. For example, for a searching algorithm, the worst case is one where the value is in the last place we check or is not in the list. This could involve comparing the key to each list value for a total of N comparisons.
3. Average Case Input Analysis:- This represents the input set that allows an algorithm to deliver an average performance. Doing Average-case analysis is a four-step process. These steps are as follows.
   1. Determine the number of different groups into which all possible input sets can be divided.
   2. Determine the probability that the input will come from each of these groups.

Suppose we have an algorithm as shown in Figure 1, and we run this algorithm on different inputs, and for every input, the running time for the algorithm is different. So, in this case, to analyse the algorithm in particular inputs, we consider three cases.

Worst-case analysis of the algorithm

It’s a case when an algorithm will take a maximum running time for input size n to execute. Let’s say we are searching for an element in an array using a searching algorithm, then if an element is found at the last index, then it’s the worst-case scenario for the algorithm. So generally, we consider an input for which the algorithm takes the longest time to execute.

Note – The worst case is very informative and is usually done because an algorithm can’t execute in a time that is greater than the worst case.

Best-case analysis of the algorithm

It’s a case when the algorithm will take the minimum running time for an input size. For example, if we search for an element in an array and we find that the array starts with the first element, of the array. Then it’s the best-case for an algorithm. So, generally, to compute the best case of an algorithm, we consider an input for which the algorithm takes the shortest time.

Note: this case is not very informative because it doesn’t show the real execution time of an algorithm.

Average case analysis of an algorithm

It’s a case when an algorithm takes an average running time for an input size n to execute. Let’s say we search for an element in an array, and the element is found in the middle of the array. Then it’s an average case for the algorithm. So, usually, to compute the average case of an algorithm, we consider all possible inputs and compute the average running time.

Note: Generally, it’s very difficult to compute the average case because the input size is very dependent on the number of terms.