recategorized by
600 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

1.4k
views
1 answers
0 votes
Ram Swaroop asked Jan 27, 2019
1,419 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 is_Answer 1.647
729
views
1 answers
1 votes
Vishal Goyal asked Dec 6, 2016
729 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 elements, if we used simple uniform hashing?
437
views
1 answers
0 votes