The Analysis of Find and Versions of it
Diether Knof, Uwe Roesler
Abstract
In the running time analysis of the algorithm Find and versions of it
appear as limiting distributions solutions of stochastic fixed points
equation of the form X D= ∑ i Ai
XiˆBi+C on the space D
of cadlag functions. The distribution of the D-valued
process X is invariant by some random linear affine
transformation of space and random time change. We show the existence
of solutions in some generality via the Weighted Branching Process.
Finite exponential moments are connected to stochastic fixed point of
supremum type X
D=
supi(AiXi+Ci)
on the positive reals. Specifically we present a running time analysis
of m-median and adapted versions of Find. The finite
dimensional distributions converge in L1 and
are continuous in the cylinder coordinates. We present the optimal
adapted version in the sense of low asymptotic average number of
comparisons. The limit distribution of the optimal adapted version of
Find is a point measure on the function [0,1]∋t↦1 +
min{t, 1-t}.
Full Text: PDF PostScript