designed to operate on strings of text). Similarly, even when a sensible description of a particular "average case" (which will probably only be applicable for some uses of the algorithm) is possible, they tend to result in more difficult analysis of equations. Worst-case analysis gives a safe analysis (the worst case is never underestimated), but one which can be overly pessimistic, since there may be no (realistic) input that would take this many steps. In some situations it may be necessary to use a pessimistic analysis in order to guarantee safety. Often however, a pessimistic analysis may be too pessimistic, so an analysis that gets closer to the real value but may be optimistic (perhaps with some known low probability of failure) can be a much more practical approach. One modern approach in academic theory to bridge the gap between worst-case and average-case analysis is called smoothed analysis. When analyzing algorithms which often take a small time to complete, but periodically require a much larger time, amortized analysis can be used to determine the worst-case running time over a (possibly infinite) series of operations. This amortized cost can be much closer to the average cost, while still providing a guaranteed upper limit on the running time. So e.g. online algorithms are frequently based on amortized analysis. The worst-case analysis is related to the worst-case complexity. 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 tables 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. Examples Sorting algorithms Insertion sort applied to a list of n elements, assumed to be all different and initially in random order. On average, half the elements in a list A1 ...