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$
2
  • 2
    $\begingroup$ Question cross-posted on SO: stackoverflow.com/questions/10471589/… Next time please include this information in the question. $\endgroup$
    – rgrig
    Commented May 7, 2012 at 10:10
  • $\begingroup$ @rgrig Looks like different askers. Presumably classmates with the same homework assignment. $\endgroup$ Commented May 7, 2012 at 22:40

2 Answers 2

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 and acknowledge you have read our privacy policy.

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