The moments of FIND
- 1 December 1997
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 34 (4) , 1079-1082
- https://doi.org/10.2307/3215021
Abstract
To study the limiting behaviour of the random running-time of the FIND algorithm, the so-called FIND process was introduced by Grübel and Rösler [1]. In this paper an approach for determining the nth moment function is presented. Applied to the second moment this provides an explicit expression for the variance.Keywords
This publication has 2 references indexed in Scilit:
- Asymptotic distribution theory for Hoare's selection algorithmAdvances in Applied Probability, 1996
- Algorithm 64: QuicksortCommunications of the ACM, 1961