Showing math.PRShow all
2 papers · 1 filter
math.PR2004
Probabilistic Analysis for Randomized Game Tree Evaluation
Tämur Ali Khan, Ralph Neininger
We give a probabilistic analysis for the randomized game tree evaluation algorithm of Snir. We first show that there exists an input such that the running time, measured as the num…
math.PR2000
Perfect simulation from the Quicksort limit distribution
Luc Devroye, James Allen Fill, Ralph Neininger
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional…