This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
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?