Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-24T17:26:29.836Z Has data issue: false hasContentIssue false
  • English
  • Français

The moments of FIND

Part of: Special processes Theory of data Distribution theory - Probability

Published online by Cambridge University Press:  14 July 2016

Volkert Paulsen
Volkert Paulsen*
Affiliation:
Universität Kiel
*
∗Postal address: Mathematisches Seminar, Universität Kiel, D–24098 Kiel, Germany.
Get access Rights & Permissions [Opens in a new window]

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

STOCHASTIC ALGORITHMSFIXED-POINT METHOD

MSC classification

Primary: 60E99: None of the above, but in this section
Secondary: 60K99: None of the above, but in this section 68P10: Searching and sorting
Type
Short Communications
Information
Journal of Applied Probability , Volume 34 , Issue 4 , December 1997 , pp. 1079 - 1082
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Grübel, R. and Rösler, U. (1996) Asymptotic distribution theory for Hoare's selection algorithm. Adv. Appl. Prob. 28, 252–269.CrossRefGoogle Scholar
[2] Grübel, R. and Rösler, U. (1995) The backward view on the algorithm FIND. Preprint. Google Scholar
[3] Hoare, C. A. R. (1961) Algorithm 63, Partition; Algorithm 64, Quicksort; Algorithm 65, Find. Commun. ACM 4, 321–322.Google Scholar