Editing In-place algorithm (section)

== Role of randomness ==
{{See also|RL (complexity)|BPL (complexity)}}
In many cases, the space requirements of an algorithm can be drastically cut by using a [[randomized algorithm]]. For example, if one wishes to know if two vertices in a graph of {{math|''n''}} vertices are in the same [[Connected component (graph theory)|connected component]] of the graph, there is no known simple, deterministic, in-place algorithm to determine this. However, if we simply start at one vertex and perform a [[random walk]] of about {{math|20''n''{{sup|3}}}} steps, the chance that we will stumble across the other vertex provided that it is in the same component is very high. Similarly, there are simple randomized in-place algorithms for primality testing such as the [[Miller–Rabin primality test]], and there are also simple in-place randomized factoring algorithms such as [[Pollard's rho algorithm]].