Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make the algorithm look bad (chosen before the hash function's random seed is known, for a specific 2-independent hash function that is also chosen to make the rest of the algorithm look bad). So it shouldn't be surprising that with two different input models you get two different results.