No, actually it does rely on deterministically placed elements. And its analyzing unix qsort which is a deterministic algorithm. Unless I'm misunderstanding th

No, actually it does rely on deterministically placed elements. And its analyzing unix qsort which is a deterministic algorithm. Unless I'm misunderstanding the paper (which I could be). The argument relies on the fact that the adversary can choose the elements on the fly. This requires the input be deterministic so that the adversary knows what elements are where. If you randomize the input, the adversary will have no knowledge of the input and thus is not able to choose which elements go in which index. This would be randomly generated. For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ Recitation 09/08 explains this problem in depth.