# Probabilistic analysis of algorithms

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Probabilistic_analysis_of_algorithms
> Markdown URL: https://mediated.wiki/source/Probabilistic_analysis_of_algorithms.md
> Source: https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms
> Source revision: 1324267450
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [analysis of algorithms](/source/analysis_of_algorithms), '''probabilistic analysis of algorithms''' is an approach to estimate the [computational complexity](/source/Analysis_of_algorithms) of an [algorithm](/source/algorithm) or a computational problem. It starts from an assumption about a [probability distribution](/source/probability_distribution) on 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 algorithm](/source/probabilistic_algorithm)s, but the two may be combined.

For non-probabilistic, more specifically [deterministic](/source/deterministic_algorithm), algorithms, the most common types of probabilistic complexity estimates are the [average-case complexity](/source/average-case_complexity)  and the almost-always complexity. 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](/source/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.

==See also==
*[Amortized analysis](/source/Amortized_analysis)
*[Average-case complexity](/source/Average-case_complexity)
*[Best, worst and average case](/source/Best%2C_worst_and_average_case)
*[Random self-reducibility](/source/Random_self-reducibility)
*[Principle of deferred decision](/source/Principle_of_deferred_decision)

== References ==
*{{citation
 | last1 = Frieze | first1 = Alan M.
 | last2 = Reed | first2 = Bruce
 | editor1-last = Habib | editor1-first = Michel
 | editor2-last = McDiarmid | editor2-first = Colin
 | editor3-last = Ramirez-Alfonsin | editor3-first = Jorge
 | editor4-last = Reed | editor4-first = Bruce
 | contribution = Probabilistic analysis of algorithms
 | doi = 10.1007/978-3-662-12788-9_2
 | isbn = 9783662127889
 | pages = 36–92
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Probabilistic Methods for Algorithmic Discrete Mathematics
 | volume = 16
 | year = 1998}}
*{{citation
 | last = Hofri | first = Micha
 | doi = 10.1007/978-1-4612-4800-2
 | isbn = 9781461248002
 | publisher = Springer
 | title = Probabilistic Analysis of Algorithms: On Computing Methodologies for Computer Algorithms Performance Evaluation
 | year = 1987}}
*{{citation
 | last = Frieze | first = A. M.
 | editor1-last = Tinhofer | editor1-first = G.
 | editor2-last = Mayr | editor2-first = E.
 | editor3-last = Noltemeier | editor3-first = H.
 | editor4-last = Syslo | editor4-first = M. M.
 | contribution = Probabilistic analysis of graph algorithms
 | doi = 10.1007/978-3-7091-9076-0_11
 | isbn = 9783709190760
 | pages = 209–233
 | publisher = Springer
 | series = Computing Supplementa
 | title = Computational Graph Theory
 | volume = 7
 | year = 1990}}

Category:Analysis of algorithms

{{algorithm-stub}}

---
Adapted from the Wikipedia article [Probabilistic analysis of algorithms](https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.