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 variant

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$.


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: Rice's method,moments,functional equation,asymptotic expansion,Skip list,[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]

1 Document citing this article

Consultation statistics

This page has been seen 184 times.
This article's PDF has been downloaded 132 times.