Analysis of a new skip list variant

Abstract

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

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]