To understand how an algorithm can perform on different sizes of input we need to analyze 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.
Analysis of algorithm
suppose we have an algorithm as shown in the given below image. and we run this algorithm on different inputs and for every input, the running time for the algorithm is different. as you see in the image. so, in this case, to analyze the algorithm in particular inputs we consider three cases.
Three cases of algorithm
- Worst case
- Best case
- Average case
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 a worst-case 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 found that array at the first element of an array. then it’s a 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 on a number of terms.
