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.
