Distinguish best-case, average-case and worst-case efficiency of an algorithm.

Best case: The best case running time of an algorithm is the function defined by the minimum number of steps taken or any instance of size n.

Beat case complexity:

(i) Minimum number of steps for any possible input.

Average case The average case running time of an average number of steps taken on any instance of size n.

Average case complexity:

(i) Average of the running times of all possible inputs.

(ii) Demands a definition of probability of each input, which is usually difficult to provide and to analyze.

Worst case: The worst case running time of an algorithm is the function defined by the maximum number of steps taken on any instance of size n.

Worst case complexity:

(i) Maximum steps the algorithm takes for any possible input.

(ii) Most tractable measure.