THE PATH-LENGTH OF RANDOM SKIP LISTS

The skip list is a recently introduced data structure that may be seen as an alternative to (digital) tries. In the present paper we analyze the path length of random skip lists asymptotically, i.e. we study th e cumulated successful search costs. In particular we derive a precise asymptotic result on the variance, being of order n2 (which is in con trast to tries under the symmetric Bernoulli model, where it is only o f order n). We also intend to present some sort of technical toolkit f or the skilful manipulation and asymptotic evaluation of generating fu nctions that appear in this context.