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.

# 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?