The Alias Method is an O(1) algorithm to select elements from a distribution

While looking up Walker's Alias Method I ended up here http://forums.udacity.com/questions/1012915/resampling-walke... , where people say it is not Walker's method, but Vode's. I can't verify it right now but I thought it might be of interest anyway.

"You could also use ranges, picking a random number between 0.0 and 1.0 and returning :win when the number is below 0.8, :lose otherwise. But, these algorithms are still O(n)"

Maybe my math is a bit rusty, but is this really O(n)? Why is that?

n here is the number of different elements you can choose from. If there was a third alternative, you'd have to add another if statement.

An excellent writeup on different techniques to do this: http://www.keithschwarz.com/darts-dice-coins/