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?