1,308 views
2 votes
2 votes
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?

1 Answer

Best answer
8 votes
8 votes

Let's choose two element i.e. the pair  nC2 ways =n(n-1)/2 =k

each pair we assume as "x"

Each pair having same probability for collision that is 1/m =p(x)

ans = $\sum_{1}^{k}x p(x)$  

      =[n(n-1)/2] * 1/m
      = [n(n-1) /2m] should be the ans..

http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/solutions-to-some-homework-exercises-as-shared-with-students/3-solutions-clrs-11.pdf
 

http://gatecse.in/w/images/7/7d/IntroductiontoAlgorithms-CormenSolution.pdf

selected by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
3
Gaurav Kadyan asked Aug 14, 2023
238 views
For merging two unsorted list of size m and n into sorted list of size m+n. The time complexity in terms of number of comparison for this is
0 votes
0 votes
1 answer
4
DAWID15 asked Dec 9, 2022
633 views
To justify the OPTION B they gave an example of 2*2 matrix. However we can see that row 2 is linearly dependent on row1. Even though the 2nd row looks non-zero it can be ...