Analysis of Skiplists

Discover the advantage of using the skiplists.

Here, we analyze the expected height, size, and length of the search path in a skiplist. This section requires a background in basic probability. Several proofs are based on the following basic observation about coin tosses.

Lemma 1: Let TT be the number of times a fair coin is tossed up to and including the first time the coin comes up heads. Then, E[T]=2.E[T] = 2.

Proof: Suppose we stop tossing the coin the first time it comes up heads. Define the indicator variable

Ii={0   if the coin is tossed less than i times1   if the coin is tossed i or more timesI_i = \begin{cases} 0 \text{\ \ \ if the coin is tossed less than $i$ times}\\ 1 \text{\ \ \ if the coin is tossed $i$ or more times} \end{cases}

Note that Ii=1I_i = 1 if and only if the first i1i -1 coin tosses are tails, so E[Ii]=Pr{Ii=1}=1/2i1.E[I_i] = \Pr \{I_i = 1\} = 1/2^{i-1}. Observe that TT , the total number of coin tosses, can be written as T=i=1Ii.T = \sum^\infty_{i = 1} I_i. Therefore,

E[T]=E[i=1Ii]=i=1E[Ii]=i=11/2i1=1+1/2+1/4+1/8+=2\begin{split} E[T] & = E \left[ \sum^\infty_{i=1} I_i \right] \\ & = \sum^\infty_{i=1} E[I_i] \\ & = \sum^\infty_{i=1} 1/2^{i-1} \\ & = 1 + 1/2 + 1/4 + 1/8 + \cdots \\ & = 2 \end{split} ...