DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

Analysis of a new skip list variant

Guy Louchard, Helmut Prodinger

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 logQ n, with Q = 1/q a parameter, it is here given by (Q+1) logQ n.

Full Text: PDF

Valid XHTML 1.0 Transitional