Guy Louchard ; Helmut Prodinger - Analysis of a new skip list variant

dmtcs:3476 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities - https://doi.org/10.46298/dmtcs.3476
Analysis of a new skip list variantConference paper

Authors: Guy Louchard 1; Helmut Prodinger 2

  • 1 Département d'Informatique [Bruxelles]
  • 2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]


For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model. While the average in Pugh's original version behaves like $Q \log_Q n$, with $Q = \frac{1}{q}$ a parameter, it is here given by $(Q+1) \log_Q n$.

https://doi.org/10.46298/dmtcs.3476
Source: HAL:hal-01184678v1
Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Section: Proceedings
Published on: January 1, 2006
Imported on: May 10, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] Skip list, Rice's method, moments, functional equation, asymptotic expansion

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 379 times.
This article's PDF has been downloaded 329 times.