To analyze the given algorithm we need to know on what inputs the algorithm is taking less time (performing well) and on what inputs the algorithm is taking huge time. We know that an algorithm can be represented in form of an expression. That means we represent the algorithm with multiple expressions: one for case where it is taking less time and other for the case where it is taking more time. In general-
Worst Case:-
- Defines the input for which the algorithm takes huge time.
- Input is the one for which the algorithm runs slower
Best Case:-
- Defines the input for which algorithm takes lowest time.
- Input is the one for which algorithm works fastest.
Average Case:-
- Provides a prediction about the running time of the algorithm.
- Assumes that the input is random.
Lower Bound <= Average Time <= Upper Bound
For a given algorithm, we can represent best, worst and average cases in the form of an expression.
Example:-
f(n) = n2 + 500, for worst case
f(n) = n + 100n + 500, for best case
Similarly, we can define the average case too.