Best, Worst and Average case complexity

 Using RAM model of computation, we can count how many steps our algorithm will take on any given input instance by simply executing it on the given input. However, to really understand how good or bad an algorithm is, we must know how it works over all instances.

1. Best case complexity

Best case Complexity gives lower bound on the running time of the algorithm for any instance of input(s). This indicate that the algorithm can never have lower running time than best case for particular class of problems.

2. Worst case complexity

Worst case complexity gives upper bound on the running time of the algorithm for all the instances of the input(s). This ensures that no input can overcome the running time limit posed by worst case coplexity.



3. Average case complexity

Average case complexity gives average number of steps required on any instance of the input(s).