__Structural Properties of Skip Lists__

__Structural Properties of Skip Lists__

Recall that *r *= 1 + *max**i**{**Z**i**}*. Notice that *Z**i **≥ **k *iﬀ the coin tossed for *k**i *gets a run of at least *k *successes right from the beginning and this happens with probability *p**k *. Since *r **≥ **k *iﬀ at least one of *Z**i **≥ **k **− *1 , we easily get the following fact from Boole’s inequality

Choosing *k *= 4 log1*/**p **n *+ 1, we immediately obtain a high conﬁdence bound for the number of levels. In fact,

We obtain an estimation for the expected value of *r*, using the formula stated in theorem ( 13.3) as follows:

*TH**E**OR**E**M 13.11 **Th**e expected number of levels in a skip list of **n **eleme**nt**s is **O*(log *n*)*.** **I**n fact, the number is **O*(log *n*) *with high probability.*

Recall that the space complexity, *| **S**L **| *is given by

Since *Z**i *is a geometric random variable with parameter *p*, *Z *is a negative binomial random variable by theorem 13.6.

This implies that 4*n *is in fact a very high conﬁdence bound for *Z*. Since *| **S**L **|*= *Z*+*n*+2*r*+2, we easily conclude that

*TH**E**OR**E**M 13.12 **Th**e space complexity of a skip list for a set of size **n **i**s **O*(*n*) *with** **ver**y high probability.*