1.2.5 Worst Case, Average Case, and Amortized Complexity

• Worst case Running Time: 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.

• 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. Computation of average-case running time entails knowing all possible input sequences, the probability distribution of occurrence of these sequences, and the running times for the individual sequences. Often it is assumed that all inputs of a given size are equally likely.

• 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 performance of each operation in the worst case.

1.

For example, consider the problem of finding the minimum element in a list of elements.

Worst case = O(n)

Average case = O(n)

2.

Quick sort

Worst case = O(n²)

Average case = O(n log n)

3.

Merge Sort, Heap Sort

Worst case = O(n log n)

Average case = O(n log n)

4.

Bubble sort

Worst case = O(n²)

Average case = O(n²)

5.

Binary Search Tree: Search for an element

Worst case = O(n)

Average case = O(log n)