The binomial transform and the analysis of skip lists

DOI10.1016/j.tcs.2005.10.041zbMath1086.68153OpenAlexW2006059832MaRDI QIDQ818124

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

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) Factorials, binomial coefficients, combinatorial functions (05A10) Data structures (68P05)

Related Items (1)

Fair priority scheduling (FPS): a process scheduling algorithm based on skip ring data structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Approximating functions by their Poisson transform
• Automatic average-case analysis of algorithms
• Some observations on skip-lists
• Average search and update costs in skip lists
• A limit theory for random skip lists
• Yet another application of a binomial recurrence. Order statistics
• Linear probing and graphs
• Combinatorics of geometrically distributed random variables: Left-to-right maxima
• 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

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