The analysis of simple list structures (Q1067775)

We present an analysis of simple lists, either sorted or unsorted, under the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of length n. Using the theory of continued fractions and orthogonal polynomials. \textit{P. Flajolet, J. Françon} and \textit{J. Vuillemin} [J. Algorithms 1, 111-141 (1980; Zbl 0445.68036)] have determined average costs of sequences of operations for many data structures of the dictionary or priority queue type. We show here that for the simplest structures variance estimates can also be obtained. The method uses continued fractions and properties of nonclassical q- generalizations of Hermite and Laguerre polynomials.