Probabilistic Analysis of Algorithms

In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm.

This approach is not the same as that of probabilistic algorithms, but the two may be combined.

For non-probabilistic, more specifically, for deterministic algorithms, the most common types of complexity estimates are

• the average-case complexity (expected time complexity), in which given an input distribution, the expected time of an algorithm is evaluated
• the almost always complexity estimates, in which given an input distribution, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds.