MadeEasy Test Series: Programming & DS - Hashing

Question

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?

Comments

https://gateoverflow.in/84285/madeeasy-testseries

Answer 1

There are nC2 pairs that may collide with probability each=1/m

i.e. (n2-n)/2m which is theta option C.