This is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.