2
$\begingroup$

A skip list

skip list example

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 analysis

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

$\endgroup$
2
$\begingroup$

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)$:

Skip List

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}$$

$\endgroup$
  • $\begingroup$ C(k) = 2k C(k) = the expected length of the path that raises k levels backward The length is only a function of level k. When I see the proof process at the first time, I cannot understand why $$ C(k) $$ in the left hand side and that in the right hand side is same in the equation $$ C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2} $$ . I think the expected length of the path is different anyway. $\endgroup$ – skytree May 14 '17 at 14:37
  • $\begingroup$ @skytreekirei, I've edited my answer to address why $C(k)$ can be on the left and right side of the recurrence. I hope this helps. $\endgroup$ – ryan May 14 '17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.