PA of Algorithms Q1

0. A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the m^th record is the first record to result in collision is

A
B
C
D

Answer
Comment
Array

Option : A
Explanation :
Probability for the first record not colliding is x/x.
Probability for the second record not colliding is x-1/x.
(This is because one place is already occupied, So, favorable number of cases is x-1).
Probability for the third record not colliding is x-2/x.
Probability for the (m-1)th record not colliding is .
Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So,

Forgot your password?

I agree with the Terms.