The analysis of simple list structures
type: Item
instance of: scholarly article
title: The analysis of simple list structures
zbMATH Open document ID: 0581.68021
DOI: 10.1016/0020-0255(86)90016-2
author: Philippe Flajolet
author: Claude Puech
author: Jean E. Vuillemin
published in: Information Sciences
publication date: 1986-01-01T00:00:00Z
full work available at URL: RR-0241.pdf
review text: 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.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68N99
zbMATH DE Number: 3930329
zbMATH Keywords: performance
zbMATH Keywords: analysis of simple lists
zbMATH Keywords: continued fractions
zbMATH Keywords: orthogonal polynomials
zbMATH Keywords: data structures
zbMATH Keywords: dictionary
zbMATH Keywords: priority queue
zbMATH Keywords: q- generalizations of Hermite and Laguerre polynomials
MaRDI profile type: Publication
OpenAlex ID: W2159186660
cites work: Stacks in a two-level store
cites work: Sequence of operations analysis for dynamic data structures
cites work: Combinatorial aspects of continued fractions
cites work: Q4155833
cites work: Über Orthogonalpolynome, die q‐Differenzengleichungen genügen
cites work: A trivial algorithm whose analysis isn't
cites work: Q4057549
cites work: The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
cites work: Sur Un Problème De Configurations Et Sur Les Fractions Continues
cites work: Q5792555
description: scientific article; zbMATH DE number 3930329