The analysis of simple list structures

DOI10.1016/0020-0255(86)90016-2MaRDI QIDQ1067775zbMATH OpenOpenAlexFDO

Authors Philippe Flajolet, Claude Puech, Jean E. Vuillemin

Publication date 1986

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/inria-00076317/file/RR-0241.pdf

zbMATH Keywords

analysis of simple listscontinued fractionsdata structuresdictionaryorthogonal polynomialsperformancepriority queueq- generalizations of Hermite and Laguerre polynomials

Mathematics Subject Classification ID

Theory of software (68N99) Data structures (68P05)

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.

Recommendations

• scientific article; zbMATH DE number 17540
• scientific article; zbMATH DE number 88934
• scientific article; zbMATH DE number 4052995
• scientific article; zbMATH DE number 3947370
• A path integral approach to data structure evolution

Cites work

• A trivial algorithm whose analysis isn't
• Combinatorial aspects of continued fractions
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3588046 (Why is no real title available?)
• scientific article; zbMATH DE number 3053340 (Why is no real title available?)
• Sequence of operations analysis for dynamic data structures
• Stacks in a two-level store
• Sur Un Problème De Configurations Et Sur Les Fractions Continues
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• Über Orthogonalpolynome, die q‐Differenzengleichungen genügen

Cited in

(11)

• Brownian motion and algorithm complexity
• Random walks, Gaussian processes and list structures
• A path integral approach to data structure evolution
• Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis
• scientific article; zbMATH DE number 3947370 (Why is no real title available?)
• scientific article; zbMATH DE number 88934 (Why is no real title available?)
• Trie size in a dynamic list structure
• scientific article; zbMATH DE number 5199066 (Why is no real title available?)
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Dynamic analysis of some relational databases parameters
• Analysis of dynamic algorithms in Knuth's model

This page was built for publication: The analysis of simple list structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067775)