Advances in Applied Probability · 1996 · 64 citations · 13 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryStochastic ProcessesLimit TheoremsRandom WalksRandomized AlgorithmsSorting AlgorithmsAsymptotic Distribution TheoryAsymptotic TheoryLimit LawsRandom PartitionsRandom Walks In Random EnvironmentReal NumbersSelection AlgorithmsStochastic Process Analysis
We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds the l th smallest in a set of n numbers. Letting n tend to infinity and considering the values l = 1, ···, n simultaneously we obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.
13
Continuous Univariate Distributions.
Yasuhiro Omori, Norman L. Johnson, S. Kotz et al. · Journal of the American Statistical Association · 1995 · 9.3K citations
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
Some Asymptotic Theory for the Bootstrap
Peter J. Bickel, David A. Freedman · The Annals of Statistics · 1981 · 1.7K citations · Full text
C. A. R. Hoare · The Computer Journal · 1962 · 755 citations · Full text
C. A. R. Hoare · Communications of the ACM · 1961 · 539 citations