GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
80 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?

asked in DS by Junior (947 points)   | 80 views

1 Answer

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

i.e. (n2-n)/2m which is theta option C.
answered by Junior (717 points)  


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,063 answers
63,297 comments
24,169 users