I need to know the complexity of the following algorithm:
Draw a set of n numbers from a larger set of m numbers, one by one, randomly, with replacement. The result may be any set of numbers as long as the size is n and the elements are different.
This is a variation of the Coupon collector's problem: we do not have to draw all m elements, any set of different numbers of size n will do.
Example:
n = 3, m = 5, result = {1,5,2} produced by successive draws 1,1,5,1,5,2 from pool {1,2,3,4,5}
What is the average time complexity of this problem?
Answer
The expected
number of trials until your collection has $n$ distinct elements is:
$${m\over m}+{m\over m-1}+{m\over m-2}+\cdots +{m\over m-n+1}. $$
No comments:
Post a Comment