The most popular kind of PRNG is the linear congruential generator.
Really? I was under the impression that we were all using the Mersenne twister these days.
Not only is LCG the most popular, it is +by far+ the most popular. rand() and Java.util.Random are both LCG. And it can be spectacularly bad. See http://www.alife.co.uk/nonrandom/
Maybe the most widely known broken PRNG :)
it's an easy exercise to show that the worst case runtime is the same as the average case
That should probably say the average case is the same as the best case.