We use a simple uniform hash function to insert 300 keys into two tables of size 1000, we use chaining at one table and linear probing at the other. We are given that the keys were mapped into 290 different cells. What is the expected time of unsuccessful search in each case?
I think that the expected time will be 300/1000 at the chaining table, and $0.5(1+(1-3/10)^2)$ at the linear probing table. Is this correct? I'm not sure how the fact that the keys were mapped into 290 different cells may change the answer.