The binomial transform and the analysis of skip lists

DOI10.1016/J.TCS.2005.10.041MaRDI QIDQ818124zbMATH OpenOpenAlexFDO

Authors Patricio V. Poblete, J. Ian Munro, Thomas Papadakis

Publication date 24 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.10.041

zbMATH Keywords

analysis of algorithmsbinomial transformskip lists

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Factorials, binomial coefficients, combinatorial functions (05A10)

Recommendations

• The binomial transform and its application to the analysis of skip lists
• Skip lists - some results on a recent data structure
• Average search and update costs in skip lists
• Biased skip lists
• A limit theory for random skip lists

Cites work

• scientific article; zbMATH DE number 3814037 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• A limit theory for random skip lists
• Approximating functions by their Poisson transform
• Automatic average-case analysis of algorithms
• Average search and update costs in skip lists
• Combinatorics of geometrically distributed random variables: Left-to-right maxima
• Linear probing and graphs
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Mellin transforms and asymptotics: Harmonic sums
• Some observations on skip-lists
• The analysis of linear probing sort by the use of a new mathematical transform
• The binomial transform and its application to the analysis of skip lists
• Yet another application of a binomial recurrence. Order statistics

Cited in

(3)

• The binomial transform and its application to the analysis of skip lists
• Skip lists - some results on a recent data structure
• Fair priority scheduling (FPS): a process scheduling algorithm based on skip ring data structure

This page was built for publication: The binomial transform and the analysis of skip lists

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