Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-29T12:15:06.146Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on continuous search algorithms

Published online by Cambridge University Press:  14 July 2016

L. E. Garey  and
R. D. Gupta
L. E. Garey*
Affiliation:
University of New Brunswick
R. D. Gupta*
Affiliation:
University of New Brunswick
*
∗Postal address: Division of Mathematics, Engineering and Computer Science, University of New Brunswick, P.O. Box 5050, St. John, N.B., Canada E2L 4L5.
∗Postal address: Division of Mathematics, Engineering and Computer Science, University of New Brunswick, P.O. Box 5050, St. John, N.B., Canada E2L 4L5.
Get access Rights & Permissions [Opens in a new window]

Abstract

Continuous random search methods with an average complexity given by O(log(1/ε)) for ε → 0 where ε is a given accuracy were presented in a recent paper. In this article an example of an O(log log(1/ε)) method is presented and illustrated.

Keywords

RANDOM SEARCHROOT LOCATION METHODSAVERAGE COMPLEXITY
Type
Short Communications
Information
Journal of Applied Probability , Volume 24 , Issue 1 , March 1987 , pp. 277 - 280
Copyright
Copyright © Applied Probability Trust 1987 

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.)

Footnotes

Supported by NSERC of Canada under grants A8196 and A4850.

References

Armenakis, A. C., Garey, L. E. and Gupta, R. D. (1984) A report on search methods for static disk files. APICS Computer Science Conference, University of New Brunswick, Canada, 9–22.Google Scholar
Burton, F. W. and Lewis, G. W. (1980) A robust variation of interpolation search. Inf. Processing Letters 10, 198–201.Google Scholar
Dowell, M. and Jarratt, P. (1972) The Pegasus method for computing the root of an equation. BIT 12, 503–508.10.1007/BF01932959Google Scholar
Perl, Y., Itai, A. and Avni, H. (1978) Interpolation search — a Log Log N search. Comm. Assoc. Comput. Mach. 21, 550–553.Google Scholar
Pfeifer, D. (1985) An average case analysis for a continuous random search algorithm. Adv. Appl. Prob. 17, 231–233.Google Scholar
Ralston, A. (1965) A First Course in Numerical Analysis. McGraw-Hill, New York.Google Scholar