Sequence of operations analysis for dynamic data structures

DOI10.1016/0196-6774(80)90020-6zbMath0445.68036OpenAlexW1967171647MaRDI 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

stacksorthogonal polynomialscontinued fractionlinear integral transformdictionariespriority queuesdata typeslinear listssymbol tablesaverage-case performance of dynamic data structuresgenerating function for integrated costs

Mathematics Subject Classification ID

Data structures (68P05) Discrete mathematics in relation to computer science (68R99) Theory of computing (68Q99)

Related Items (24)

Improved bounds for colouring circle graphs ⋮ 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 ⋮ Topological classification and enumeration of RNA structures by genus ⋮ Analysis of dynamic algorithms in Knuth's model ⋮ Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions ⋮ On congruences and continued fractions for some classical combinatorial quantities ⋮ A combinatorial approach to nonlinear functional expansions: An introduction with an example ⋮ Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence ⋮ A path integral approach to data structure evolution ⋮ Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis ⋮ Dynamic analysis of some relational databases parameters ⋮ Enumeration of 4-regular one-face maps ⋮ On the principal recurrence of data structures organization and orthogonal polynomials ⋮ Connected chord diagrams and bridgeless maps ⋮ Formulae for Askey-Wilson moments and enumeration of staircase tableaux ⋮ Maximum queue size and hashing with lazy deletion ⋮ Trie size in a dynamic list structure ⋮ The analysis of simple list structures ⋮ Basic analytic combinatorics of directed lattice paths ⋮ Non-overlapping partitions, continued fractions, Bessel functions and a divergent series ⋮ 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)

This page was built for publication: Sequence of operations analysis for dynamic data structures