Editing Best, worst and average case (section)

== Practical consequences ==
Many algorithms with bad worst-case performance have good average-case performance.  For problems we want to solve, this is a good thing: we can hope that the particular instances we care about are average.  For [[cryptography]], this is very bad: we want typical instances of a cryptographic problem to be hard.  Here methods like [[random self-reducibility]] can be used for some specific problems to show that the worst case is no harder than the average case, or, equivalently, that the average case is no easier than the worst case.

On the other hand, some data structures like [[hash table]]s have very poor worst-case behaviors, but a well written hash table of sufficient size will statistically never give the worst case; the average number of operations performed follows an exponential decay curve, and so the run time of an operation is statistically bounded.