It starts from an assumption about a probabilistic distribution of the set of all possible inputs.
This approach is not the same as that of probabilistic algorithms, but the two may be combined.
To obtain the average-case complexity, given an input distribution, the expected time of an algorithm is evaluated, whereas for the almost-always complexity estimate, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds.
In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or average of all possible choices in randomized steps is also taken into account, in addition to the input distributions.
This algorithms or data structures-related article is a stub.