A Band and Bound Technique for Simple Random Algorithms

27 July 1990

journal article
research article
Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences

Vol. 4 (3) , 333-344
https://doi.org/10.1017/s0269964800001649

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.

Keywords

This publication has 1 reference indexed in Scilit:

Probabilistic Analysis of Algorithms
Published by Springer Nature ,1987