(a) Let d > 2 be a fixed positive integer. consider a perfect SkipList constructed as follows: In order to create the ith level Li of the SkipList, we scan the keys of level Li1, and promote to Li every dth key. So for example, the perfect SkipList discussed in class uses the value d = 2. The case d = 3 implies that every third key is promoted, and so on. Express your answer as a function of n and d

i. What is the number of levels, as a function of n and k?

ii. What is the worst case time for performing find(x) operation ? For delete(x), For insert(x) ?

iii. Assume n = 109 . Compare the case d = 2 vs. d = d = 10 vs. d = 1000. When will the search time be optimal.

(b) Assume that we re-create a SkipList by inserting n keys, in the same order, but this time we are using the randomized insertion algorithm shown on the slides. However a key that appears in level i is promoted to level i+ 1 with probability p = 0.1 (rather than p = 0.5 that was discussed on the slides). Will the expected time to perform find(x) operation increase or decrease, compared to the expected time for the same operation in the original SkipList created with p = 0.5.