in DS recategorized by
355 views
0 votes
0 votes



anybody give detailed explnation please

in DS recategorized by
355 views

1 comment

0
0

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 .