On 11/17/2013 02:07 AM, Ivan Kazmenko wrote: > The random pick fails in the following sense: if we seed the RNG, > construct a killer case, and then start with the same seed, we get > Theta(n^2) behavior reproduced. Hence, in no sense. This does not perform independent uniform random picks.