Problem 35

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# 2-level skip list

Due: February 8
Points: 3

In class, we saw that the "optimal" skip list will have n nodes on level 0, then $$\frac{n}{2}$$ nodes on level 1, $$\frac{n}{4}$$ on level 2, and so on until there is just $$\frac{n}{2^{\lg n}} = 1$$ node on the top level, level $$\lg n$$.

This is if the height of the skip list is allowed to be as large as we want; we would want it to be roughly $$\lg n$$ so that the expected cost of searching, inserting, or deleting any node would be $$\Theta(\log n)$$, which is the best possible.

But what if the height of the skip list was limited to 2, so that the only levels with any nodes are level 0 and level 1? Describe the optimal way to construct a skip list with this restriction, if you want to store a total of n items.

Demonstrate your construction on an example of size 15 or so, and tell me what the worst-case running time of insert, delete, or search would be, in terms of n. (I want a big-O analysis.)

Note: I'm not asking for a randomized algorithm here! Just tell me how you would set up the skip list with height equal to 2, given n items.