The binomial transform and the analysis of skip lists

Abstract

To any sequence of real numbers < a(n)>(n >= 0), we can associate another sequence < a(s)>(s >= 0), which Knuth calls its binomial transform. This transform is defined through the rule

as = Bsan = Sigma(n) (-1)(n) ((s)(n)) a(n).

We study the properties of this transform, obtaining rules for its manipulation and a table of transforms, that allow us to invert many transforms by inspection.

We use these methods to perform a detailed analysis of skip lists, a probabilistic data structure introduced by Pugh as an altemative to balanced trees. In particular, we obtain the mean and variance for the cost of searching for the first or the last element in the list (confirming results obtained previously by other methods), and also for the cost of searching for a random element (whose variance was not known).

We obtain exact solutions, although not always in closed form. From them we are able to find the corresponding asymptotic expressions.