# Average operations on a hashtable

Suppose we are given an empty hash table of size $n$, where collisions are resolved by re-hashing (open addressing).

Next, $n/2$ items are randomly inserted into the table using a hash function that provides uniform distribution of hash values.

On average, how many operations are needed to randomly add additional $n/2$ items to the above table? How would I approach to such calculations?

Thanks

• Wouldn't it depend on how the re-hashing is done? To check that I understand correctly: First you add $n/2$ items, and you want to know the number of operations required if you then add another $n/2$ items? (Presumably you're looking for the expected value of that number?) – joriki Jul 3 '15 at 7:52
• Yes, thats correct. – Boris Ablamunits Jul 3 '15 at 8:19
• So will you tell us how the re-hashing is done? – joriki Jul 3 '15 at 8:54
• Unfortunately it is not specified in the problem. I was thinking (although I am not sure at all) of somehow trying to base an answer on the fact that if a hashing table is of size m, and already contains k items - the expected number of operations when inserting the k+1 item is (m+1)/(m-k+1). I am not sure it is the right direction and im finding it hard to get my head around it. – Boris Ablamunits Jul 3 '15 at 9:12
• Why isn't it $m/(m-k)$? For the $m$th item, it should be $m$, not $m+1$, no? – joriki Jul 3 '15 at 9:16