Next: 1.2.6 Big Omega and Big Theta Notations
Up: 1.2 Complexity of Algorithms
Previous: 1.2.4 Role of the Constant
 Worst case Running Time:
The behavior of the algorithm with respect to
the worst possible case of the input instance.
The worstcase 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 averagecase running time of an algorithm is an estimate of the running
time for an "average" input. Computation of averagecase 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^{2})

 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^{2})

 Average case = O(n^{2})
 5.
 Binary Search Tree: Search for an element

 Worst case = O(n)

 Average case = O(log n)
Next: 1.2.6 Big Omega and Big Theta Notations
Up: 1.2 Complexity of Algorithms
Previous: 1.2.4 Role of the Constant
eEL,CSA_Dept,IISc,Bangalore