03-6   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Uwe Rösler:

The backward view on the algorithm FIND

FIND is a random divide and conquer algorithm to find the k'th largest element in a set. We provide here an analysis of FIND using contraction arguments on the space of measures only. We provide stochastic upper bounds for FIND's runtime. The limiting distribution of FIND's runtime, correctly normalized, is characterized as a fixed point. The key fixed point equation allows further analysis of the distribution, like moments or tail behavior.

Mathematics Subject Classification (1991): Primary 60F05, Secondary 68P10, 60K99

Keywords: FIND, divide and conquer algorithm, random algorithm, Mallow metric, stochastic order, limiting distribution, contraction

Mail an Jens Burmeister
[Thu Feb 19 18:56:36 2009]
Impressum