Sequence of operations analysis for dynamic data structures

DOI10.1016/0196-6774(80)90020-6zbMath0445.68036MaRDI QIDQ3890114

Philippe Flajolet, Jean Francon, Jean E. Vuillemin

Publication date: 1980

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(80)90020-6

zbMATH Keywords

stacks; orthogonal polynomials; continued fraction; linear integral transform; dictionaries; priority queues; data types; linear lists; symbol tables; average-case performance of dynamic data structures; generating function for integrated costs

Mathematics Subject Classification ID

68P05: Data structures

68R99: Discrete mathematics in relation to computer science

68Q99: Theory of computing

Related Items

Trie size in a dynamic list structure, Improved bounds for colouring circle graphs, Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions, Topological classification and enumeration of RNA structures by genus, Enumeration of 4-regular one-face maps, Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence, Dynamic analysis of some relational databases parameters, Maximum queue size and hashing with lazy deletion, Non-overlapping partitions, continued fractions, Bessel functions and a divergent series, Analysis of dynamic algorithms in Knuth's model, The analysis of simple list structures, Path generating functions and continued fractions, Über die Koeffizienten der Stieltjes-Matrix eines Jacobi-Kettenbruchs. (On the coefficients of the Stieltjes matrix of a Jacobi continued fraction), On congruences and continued fractions for some classical combinatorial quantities, A combinatorial approach to nonlinear functional expansions: An introduction with an example, A path integral approach to data structure evolution, Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis, Basic analytic combinatorics of directed lattice paths, A bijective proof of a Touchard-Riordan formula, Combinatorial theory of \(\text{T}\)-fractions and two points Padé approximants, Large deviations for combinatorial distributions. I: Central limit theorems, Connected chord diagrams and bridgeless maps, On the principal recurrence of data structures organization and orthogonal polynomials, Formulae for Askey-Wilson moments and enumeration of staircase tableaux