Randomized algorithm

Remarks

Example: randomized quicksort chooses each pivot uniformly at random among the current items. It always returns the sorted list, so it is Las Vegas, and its expected number of comparisons is $O(n \log n)$ for every input of $n$ distinct items.

Example: to test whether $AB = C$ for $n \times n$ matrices, Freivalds' algorithm picks a random vector $v \in \set{0, 1}^n$ and checks $A(Bv) = Cv$ in time $O(n^2)$. If $AB = C$ it always says yes; if $AB \ne C$ it says yes with probability at most $1/2$, so it is Monte Carlo with one-sided error.

Non-example: an algorithm that runs on a fixed pseudorandom seed stored in its code makes no random choices, so it is deterministic.

The error probability of a Monte Carlo algorithm can be reduced by running it several times with independent random bits.