355 views

### 1 comment

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 .

1
927 views