# What is the value of p that minimizes the preceding expression?

Suppose that, instead of promoting an element from L_{i-1} into L_{i} based on a coin toss, we promote it with some probability p, 0 < p < 1.

1. Show that, with this modification, the expected length of a search path is at most (1/p) log_{1/p} n + *O(*1).

2. What is the value of p that minimizes the preceding expression?

3. What is the expected height of the skiplist?

4. What is the expected number of nodes in the skiplist?