Chapter 5

So long as it can do so, the adversary will assign values to new keys involved in a comparison so as to put keys on opposite sides of median. The adversary may not assign values larger than median to more than (n-1)/2 keys, nor values smaller than median to more than (n-1)/2 keys. Any two values can be placed on either side of the initial median. ................
................