ANSWER ALL THREE QUESTIONS

The W. Pugh article on skip lists suggests that an appropriate value to set MaxLevel to is L(N) where N is an upper bound on the number of elements in the list and L() is the function de ned in the article and lecture notes. 1. Why is this a reasonable strategy? Please provide some justi cation in terms of the space complexity and the average time complexity. 2. If you used this strategy to set MaxLevel, what is the worst-case space com- plexity of the skip list? Please justify your answer. 3. Assume your system has space for at most phi total number of pointers in any skip list with at most N elements. If you are setting MaxLevel to L(N), what is the maximum value that you should set p to be to ensure that you do not have more than phi pointers. (You may ignore the pointers in the head element). Please show all the steps of your derivation.