Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

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

Antonio

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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2019-08-20 01:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If you were the first to set foot on the Moon, what would be your epigram?






    Results (142 votes). Check out past polls.

    Notices?