Comment by hvidgaard

It would be fairly simple to create an argument he cannot refute. Make a hashtable with 4 slots, put 16 elements in it, even with perfect distribution it would have to look through 4 elements to find the last one. This means it takes O(1/4n), or, since constants doesn't matter O(n). If he cannot accept that I would simply walk out and inform them that I could not take the job seriously, when the interviewer don't know such a basic thing.