# Expected space consumption of skip lists

What is the expected space used by the skip list after inserting $n$ elements?

I expect that in the worst case the space consumption may grow indeﬁnitely.

Wikipedia says space $O(n)$.

How can this be proven one way or another?

In this paper it is proven that there exists a constant $\alpha$ such that the probability of the space exceeding $\alpha n$, is less than $1/2^{\Omega(\sqrt{n})}$. Thefore, the more elements there are, the less likely it is to exceed this space bound.

If you really want worst case bounds, and not expected bounds, then take a look at the deterministic skip list which has better space performance than popular balanced binary tree implementations (i.e. $\theta(n)$ with better constants).

However, if you want a random skip list, then technically the worst-case space consumption used by a random skip-list is in fact unbounded. However, the probability that we need a large amount of space is vanishingly small. For large $n$, it would be more likely that you have a hardware failure and simultaneously win the lottery than the skip-list would use, say $n^2$ space.

In more concrete terms, we can evaluate the tail bounds on the expected space consumption of the skip-list. How likely is it that the space used differs significantly from the mean of $\theta(n)$?

Recall that a skip-list (original paper) is made up of several layers. We begin with all elements in the first layer, and for each element, we flip a coin, and promote it to the next layer with probability $1/2$. We continue promoting elements until we reach a layer from which no elements are promoted. Therefore each element belongs to layer $L_i$ with probability $1/2^i$, since each promotion is an i.i.d. coin flip with probability $1/2$.

Furthermore, note that the total number of elements in all layers is distributed according to the negative binomial distribution with parameters ($n$, $1/2$). That is, the number of successes (heads) in a sequence of Bernoulli trials (coin flips) until we have $n$ failures (tails) corresponds exactly to the total number of promotions when constructing the skip list. Therefore, the expected number of promotions is $n$.

In these lecture notes, they give tail bounds for the number of trials $Y$ in a negative binomial distribution (until we see $n$ tails) where $k = \frac{n}{(1-\delta)p}$.

$$P(Y > k) \leq e^{-\delta^2n/(3(1-\delta))}$$

Letting $\delta = 1/3$ and $p = 1/2$, we see that $$P(Y > 3n) < e^{-n\cdot(2/81)} = 1/e^{\theta(n)}$$

Thus, the probability that there are more than $3n$ elements in the skip-list is $o(2^{-n})$. When we have a tail bound like this, we say that the space consumption is linear with very high probability.