# Best Case, Worst Case, Average Case, and Amortized Complexity

**1) Best case Running Time**: is the minimum number of steps that an

algorithm can take any collection of data values. Smaller Comparisons. In

Big Oh Notation (1) is considered as best case efficiency.

**2) Worst case Running Time**: is the maximum number of steps that an

algorithm can take for any collection of data values. Maximum number of

comparisons. The behavior of the algorithm with respect to the worst

possible case of the input instance. The worst case running time of an

algorithm is an upper bound on the running time for any input. Knowing it

gives us a guarantee that the algorithm will never take any longer. There is

no need to make an educated guess about the running time.

**3) Average case Running Time**: The expected behavior when the input is

randomly drawn from a given distribution. The average case running time of

an algorithm is an estimate of the running time for an average input.

Minimum number of comparisons=1

Maximum number of comparisons = n

Therefore, average number of comparisons = (n+1)/2

(n + 1)/2 is a linear function of n.

Therefore, the average case efficiency will be expressed as O(n).

**4) Amortized Running Time**: Here the time required to perform a sequence

of (related) operations is averaged over all the operations performed.

Amortized analysis can be used to show that the average cost of an operation

is small, if one averages over a sequence of operations, even though a simple

operation might be expensive. Amortized analysis guarantees the average

the performance of each operation in the worst case.

Algo

## 1 comments:

Feel free to contact the admin for any suggestions and help.