A randomized algorithm is an algorithm whose execution uses random choices (Black 2019). A mathematical model commonly supplies independent fair binary digits in addition to the input. The output and computation time may therefore vary between executions on the same input.

A bounded-error randomized algorithm is allowed to return an incorrect result with at most a specified probability on each input. For example, an error bound of requires success with probability at least for every input. An always-correct randomized algorithm permits variation in computation time while requiring correct output whenever it terminates.

A bound on the expectation value of the computation time allows occasional longer runs, whereas a bound for every sequence of random choices limits every run.

See also

Algorithm, Computation Time, Logarithmic Space, Query Complexity

Explore with Wolfram|Alpha

References

Black, P. E. "Randomized Algorithm." In Dictionary of Algorithms and Data Structures (Ed. P. E. Black). National Institute of Standards and Technology, Feb. 28, 2019. https://xlinux.nist.gov/dads/HTML/randomizedAlgo.html.

Cite this as:

Weisstein, Eric W. "Randomized Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RandomizedAlgorithm.html

Subject classifications