Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-28T16:51:26.074Z Has data issue: false hasContentIssue false
  • English
  • Français

A Band and Bound Technique for Simple Random Algorithms

Published online by Cambridge University Press:  27 July 2009

Vernon Rego
Vernon Rego
Affiliation:
Department of Computer SciencesPurdue University West Lafayette, Indiana 47907
Get access Rights & Permissions [Opens in a new window]

Abstract

A simple random algorithm (SRA) is an algorithm whose behavior is governed by a first-order Markov chain. The expected time complexity of an SRA, given its initial state, is essentially the time to absorption of the underlying chain. The standard approach in computing the expected runtime is numerical. Under certain conditions on the probability transition matrix of an SRA, bounds on its expected runtime can be obtained using simple probabilistic arguments. In particular, one can obtain upper and lower (average time) logarithmic bounds for certain algorithms based on SRAs.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 3 , July 1990 , pp. 333 - 344
Copyright
Copyright © Cambridge University Press 1990

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

REFERENCES

Hofri, M. (1987). Probabilistic analysis of algorithms. New York: Springer-Verlag.CrossRefGoogle Scholar
Knuth, D. (1972). The art of computer programming, Vol. 3, Sorting and searching. Reading, Mass.: Addison-Wesley.Google Scholar
Ross, S.M. (1983). Stochastic processes. New York: J. Wiley.Google Scholar
Stavskaya, O. & Pyatetskii-Shapiro, I. (1968). On certain properties of homogeneous nets of spontaneously active elements. Problemi Cibernetiki 20:91–106.Google Scholar