A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is
A. | (x-1) (x-2) ... (x-(m-2)) (m-1)/xm-4 |
B. | (x-1) (x-2(... (x-(m-1()(m-1)/xm-1 |
C. | (x-1) (x-2) ... (x-(m-2))(m-1)/xm |
D. | (x-1)(x-2)...(x-(m-1))(m-1)/xm |
Answer : 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, favourbale 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 x-(m-2)/x. Now the next (mth) record is resulting in a collision. Out of the x places, it should hast to one of the (m-1) places already, filled. So probability is (m-1)/x. The required probability is (x/x) (x-1/x) (x-2/x) ... (x-(m-2)/x) (m-1/x) |
|
Option: A Explanation : Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. |