recategorized by
534 views

1 Answer

0 votes
0 votes

There are n distinct elements(keys) to be inserted but only m positions available. This means number of possible hash values is m. Every key will map to one of these m values.

Considering n>m , on average there could be (n/m) collisions for the same hash value.

This means for every key , there are (n/m) others competing for the same hash value.

This gives number of such collision pairs on average $\Theta (n*n/m)$ which is option .

Related questions

0 votes
0 votes
1 answer
1
Ram Swaroop asked Jan 27, 2019
1,263 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
1 votes
1 votes
1 answer
3
Vishal Goyal asked Dec 6, 2016
671 views
Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’. What is the expected number of colliding pairs of element...
0 votes
0 votes
1 answer
4