4
$\begingroup$

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

Wikipedia says space $O(n)$.

How can this be proven one way or another?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.