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 probability distribution on the set of all possible inputs.