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