I'm taking a data-structure class, and the lecturer made the following assertion:
the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.
No proof was given, so I tried to get one myself. However, I'm stuck.
My approach at the moment: I try to show that if I swap two adjacent keys the number of attempts doesn't change. I get the idea behind it, and I think it's going in the right direction, but I can't manage to make it into a rigorous proof.
Aside, does this fact also hold for other probing techniques such as quadratic or double hashing?