to understand how an algorithm can perform on different sizes of input we need to analyze the algorithm on different cases. and to computing the best, average, and worst running time of an algorithm we need to consider three cases of an 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.
let's say if we are searching 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.
for example, if we search an element into 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 computer 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's doesn't show the real execution time of an algorithm.
let's say if we searching an element in an array and the element found in the middle of the array. then it's an average case for the algorithm.
so usually to computer average case of an algorithm, we consider all possible inputs a computer average running time.
Note: generally it's very difficult to compute the average case. because the input size is very.
Worst average and Best-case 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 algorithm
it's is a case when an algorithm will take a maximum running time for input size n to execute.let's say if we are searching 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 algorithm
it's a case when the algorithm will take the minimum running time for an input size.for example, if we search an element into 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 computer 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's doesn't show the real execution time of an algorithm.
Average case analysis of algorithm
it's a case when an algorithm takes average running time for an input size n to execute.let's say if we searching an element in an array and the element found in the middle of the array. then it's an average case for the algorithm.
so usually to computer average case of an algorithm, we consider all possible inputs a computer average running time.
Note: generally it's very difficult to compute the average case. because the input size is very.
0 Comments