Wednesday, 31 May 2017

Time complexity of variation on Coupon's collector problem



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...