# Problem 49

# k-level skip list

**Due**: March 1

**Points**: 2

(Note: you should probably start by doing Problem 41.)

What if a skip list were restricted to *k* levels, for some constant *k*? What would be the optimum way of storing *n* items in a skip-list of height *k*, and what would the resulting cost of search, insert, and delete be?

Describe the data structure construction (briefly). Give a big-O bound in terms of *n* and *k*. Then show how this relates to the usual skip list with expected height \(k = \lg n\).