http://www.perlmonks.org?node_id=158748


in reply to Re: Rolling a biased die
in thread Rolling a biased die

The problem is: It's still not truely O(1). For a lot of distrobutions, it will be really close, but you still have to pay an extra cost to resolve th conflicts on all the transition points -- it may seem like that would be inconsequential to the run time, but it really depends on what is important to you. (Example: If you roll the die m times, and your frequencies are such that 1 roll out every k requires a transition point, and picking the riht number at a transtion requires t time, then the run time is O(1 + t(m/k)) ... even if t is 1 (constant time) that's breaks down to O(m/k) which is probably worse then O(n))
Actually, O(1)=O(k) for any constant k, because the O(*) expression "eats" all constant multiplicative factors. Furthermore, you can't put the number of tries in the complexity count and expect it to remain constant. Even if a single computation requires just one CPU cicle, the complexity for computing m is O(m). I believe MeowChow asked for a solution with constant execution time regardless of the number of faces of the die and not of the number of rolls.

Best regards

Antonio