Running time of randomized algorithms
Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and&nbsp;$2^k$.  With probability at least&nbsp;$\tfrac{1}{2}$, $0\leq r &lt; n$ so use that as your answer; otherwise, try again. If you've not succeeded after&nbsp;$t$ attempts, reject your input.  The probability of this happening is at most $2^{-t}$, which can be made as small as you like and is a component of the probability that the machine gives the wrong answer.