2-level skip list

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.