Worst, Average and Best Case in Algorithms

Lets take an example of Linear Search and analyze it using Asymptotic analysis.

We can have three cases to analyze an algorithm:
1) Worst Case
2) Average Case
3) Best Case


Worst Case Analysis (Usually Done)
In this, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched is not present in the array. When the element is not present, search() functions compares it with all the elements of array one by one.

Therefore, the worst case time complexity of linear search would be Θ(n).


Average Case Analysis (Sometimes done) 
In this, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of element not being present in the array).

So we sum all the cases and divide the sum by (n+1).


Best Case Analysis (Bogus) 
In this, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when the element is present at the first location.

So time complexity in the best case would be Θ(1)