Probabilistic Analysis

Probabilistic Analysis is the use of probability in the analysis of problems. Most commonly, we use probablistic analysis to analyze the running time of an algorithm, sometimes, we use it to analyze other quantities.

In order to perform a probablistic analysis, we must use knowledge of, or make assumptions about, the distribution of the inputs.

Then we analyze our algorithm, computing an average-case running time, where we take the average over the distribution of the possible inputs. Thus we are, in effect, averaging the running time over all possible inputs.