Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re: Re: Rolling a biased die

by abell (Chaplain)
on Apr 13, 2002 at 09:08 UTC ( #158748=note: print w/replies, xml ) Need Help??

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


Replies are listed 'Best First'.
Re: Re: Re: Rolling a biased die
by hossman (Prior) on Apr 13, 2002 at 18:51 UTC
    My bad ... you're totally right.

    I don't know what i was thinking when i did that calculation. Even if every bucket is a transition point, resolving the transtion only requires that you pick between the two possible (weighted) values for that bucket.

    O(1 + k) = O(1)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://158748]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2019-01-21 06:03 GMT
Find Nodes?
    Voting Booth?
    After Perl5, I'm mostly interested in:

    Results (352 votes). Check out past polls.

    • (Sep 10, 2018 at 22:53 UTC) Welcome new users!