Probability that a hash table using chaining for collision resolution has a chain of atleast 3 out of 4 keys.

why option c is wrong becoz making of atleast 3 chain size it will probability of 1/8 ?

1Comment
shivani @shivani1234
20 Aug 2017 10:44 am

Since , it is given 4 keys are there , then we can say that chain of size 3 and 4 can be obtained.

  • Let us consider chain of size 3, then P(chain is of size 3) = 8C1 * 4C3 *7C1/84 //   8C1 for select ing 1st slot for a chain of length 3 ,4C3  for selecting 3 out of 4 keys to form chain ,7C1  for selecting 2 nd slot for holding 1 key 
  • Let us consider chain of size 4, then P(chain is of size 4) = 8C1 /84 
  • P = 8C1 * 4C3 *7C1/84  8C1 /84
    29/ 83