Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- 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,
- Option : B
- Explanation : Recursively applying the relation, we finally get T(n + 1) = c(n - 1) + T(1) = c(n - 1) + d hence order is n.
