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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy