ECCC-Report TR04-059https://eccc.weizmann.ac.il/report/2004/059Comments and Revisions published for TR04-059en-usFri, 16 Jul 2004 21:42:27 +0300
Paper TR04-059
| Randomized Quicksort and the Entropy of the Random Number Generator |
Beatrice List,
Markus Maucher,
Uwe SchÃ¶ning,
Rainer Schuler
https://eccc.weizmann.ac.il/report/2004/059The worst-case complexity of an implementation of Quicksort depends
on the random number generator that is used to select the pivot
elements. In this paper we estimate the expected number of
comparisons of Quicksort as a function in the entropy of the random
source. We give upper and lower bounds and show that the expected
number of comparisons increases from n*log(n) to n^2, if the
entropy of the random source is bounded. As examples we show
explicit bounds for distributions with bounded min-entropy, the
geometrical distribution and the delta-random source.
Fri, 16 Jul 2004 21:42:27 +0300https://eccc.weizmann.ac.il/report/2004/059