# 4.4 Analysis of Skiplists

In this section, 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 4..2   Let be the number of times a fair coin is tossed up to and including the first time the coin comes up heads. Then .

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

Note that if and only if the first coin tosses are tails, so . Observe that , the total number of coin tosses, can be written as . Therefore,

The next two lemmata tell us that skiplists have linear size:

Lemma 4..3   The expected number of nodes in a skiplist containing elements, not including occurrences of the sentinel, is .

Proof. The probability that any particular element, , is included in list is , so the expected number of nodes in is .4.2 Therefore, the total expected number of nodes in all lists is

Lemma 4..4   The expected height of a skiplist containing elements is at most .

Proof. For each , define the indicator random variable

The height, , of the skiplist is then given by

Note that is never more than the length, , of , so

Therefore, we have

Lemma 4..5   The expected number of nodes in a skiplist containing elements, including all occurrences of the sentinel, is .

Proof. By Lemma 4.3, the expected number of nodes, not including the sentinel, is . The number of occurrences of the sentinel is equal to the height, , of the skiplist so, by Lemma 4.4 the expected number of occurrences of the sentinel is at most .

Lemma 4..6   The expected length of a search path in a skiplist is at most .

Proof. The easiest way to see this is to consider the reverse search path for a node, . This path starts at the predecessor of in . At any point in time, if the path can go up a level, then it does. If it cannot go up a level then it goes left. Thinking about this for a few moments will convince us that the reverse search path for is identical to the search path for , except that it is reversed.

The number of nodes that the reverse search path visits at a particular level, , is related to the following experiment: Toss a coin. If the coin comes up as heads, then move up and stop. Otherwise, move left and repeat the experiment. The number of coin tosses before the heads represents the number of steps to the left that a reverse search path takes at a particular level.4.3 Lemma 4.2 tells us that the expected number of coin tosses before the first heads is 1.

Let denote the number of steps the forward search path takes at level that go to the right. We have just argued that . Furthermore, , since we can't take more steps in than the length of , so

We can now finish as in the proof of Lemma 4.4. Let be the length of the search path for some node, , in a skiplist, and let be the height of the skiplist. Then

The following theorem summarizes the results in this section:

Theorem 4..3   A skiplist containing elements has expected size and the expected length of the search path for any particular element is at most .

#### Footnotes

....4.2
See Section 1.3.4 to see how this is derived using indicator variables and linearity of expectation.
... level.4.3
Note that this might overcount the number of steps to the left, since the experiment should end either at the first heads or when the search path reaches the sentinel, whichever comes first. This is not a problem since the lemma is only stating an upper bound.
opendatastructures.org