This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 55

Limiting skip list height

Due: March 1
Points: 1

We have observed that the worst-case performance of a skip list is actually unbounded. Even with a single insertion, the height could grow to be arbitrarily large.

To avoid this behavior, we might explicitly limit the maximum height of new node being inserted to something like \(\lg n\). Does this seem like a good idea to you? Why or why not?