Expected Time for LookUpSkipList

Question

A skip list

Let C(k) = the expected length of the path that raises k levels backwards.

Thus C(0) = 0

For any node P in the path, with k levels higher to go, there are two cases:

1. P is a node of level i and proceeds backwards to a node of at least level i and still k levels to go

2. P is a node at a level higher than i and must yet rise (k-1) levels

Each of these two cases has a probability of 0.5

Why C(k) = 2k and how to interpret this formula? Is the analysis formula in the figure right?

Answer 1

The recurrence can be solved as: $$ \begin{align} C(k) &= \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}\\ 2 \cdot C(k) &= 1 + C(k) + 1 + C(k-1)\\ C(k) &= 1 + 1 + C(k-1)\\ C(k) &= 2 + C(k-1)\\ \end{align} $$ Then this can clearly be expanded to a summation: $$ \begin{align} C(k) &= 2 + C(k-1)\\ &= 2 + 2 + C(k - 2)\\ &= 2 + 2 + 2 + C(k - 3)\\ & \dots\\ &= 2 + 2 + \dots + C(1)\\ &= 2k\\ \end{align} $$

I haven't done much investigation into skip lists, but the math you've shown checks out. ✓

EDIT

The reason $C(k)$ appears in the left and right side of the equation, which seems concerning, is because of the Skip List structure. Take this procedure (source) to $find(86)$:

Now let's consider the reverse of this path. Notice we always move up if we can. So for any node in the reverse path, we can either (1) move up or (2) move left:

1. We move up. Now we have $C(k-1)$ more levels up to go: $$1 + C(k - 1)$$

2. We move left. We have made no progress upwards, therefore we still have $C(k)$ more levels up to go: $$1 + C(k)$$

For a randomized skip list, either of these scenarios occurs with probability $\frac{1}{2}$. This is how we get the final recurrence:

$$C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}$$