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