Average-Case Analysis

As everybody knows, there are optimistic, pessimistic, and probabilistic people. Optimistic people always hope for the best, pessimistic people are assuming the worst-case (probably not always, otherwise they wouldn't leave their bed), and probabilistic people may be characterized by judging everything by experience, i.e, assuming an average-case behavior.

Thus, when analyzing the complexity of an algorithm, we have to respect the different needs people have. That is, we should determine the minimum value (for the optimists), the maximum value (for the pessimists) and the expected value for the probabilistic fraction of our community.

This page is still under construction.