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 comment:

  1. Suresh KUMAR MukhiyaMay 14, 2013 at 4:24 AM

    Good but post in question format like, Explain the meaning of

    Best Case, Worst Case, Average Case, in algorithm complexity.

    ReplyDelete

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