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