https://gateoverflow.in/84285/madeeasy-testseries may this help

Dark Mode

355 views

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 **C **.