Worst, Average, and Best Case Analysis of Algorithms

In the previous post, we discussed how asymptotic analysis overcomes the problems of the naive way of analyzing algorithms. Now let us learn about what the worst, average, and best cases of an algorithm are:

1. Worst Case Analysis (Mostly used)

In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed.

For

Linear Search, the worst case happens when the element to be searched (x) is not present in the array. When x is not present, the search() function compares it with all the elements of arr[] one by one.

This is the most commonly used analysis of algorithms (We will be discussing below why). Most of the time we consider the case that causes maximum operations.

2. Best Case Analysis (Very Rarely used)

In the best-case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case that causes a minimum number of operations to be executed.

For

linear search, the best case occurs when x is present at the first location. The number of operations in the best…