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:
mm+mm−1+mm−2+⋯+mm−n+1.
No comments:
Post a Comment