Here is how the SkipList is set up (b) Assume that we re-create a SkipList by in
ID: 3890729 • Letter: H
Question
Here is how the SkipList is set up
(b) Assume that we re-create a SkipList by inserting n keys, in the same order, but this time we are using the randomized insertion algorithm shown on the slides. However a key that appears in level i is promoted to level i+ 1 with probability p = 0.1 (rather than p = 0.5 that was discussed on the slides) ill the expected time to perform find(x) operation increase or decrease, compared to the expected time for the same operation in the original SkipList created with p 0.5.Explanation / Answer
Each node in level i-1 will appear in level i with some probability.searching for a particular element starts with the highest level moving to the next down level if the element is not found and continues so on.
The average search time is given by
O (log n (1 / (1p) log 1/p))
with very small probability the nodes will be at every level,
skip list will degenerate to an ordinary linked list.
for p=0.5
the number of levels expected are o(logn)
nodes at level1 =n/2
nodes at level 2=n/4..
...
nodes at level n=1
for increase in levels with probability 0.5 we have
to walk up to j levels
c(j)=1+0.5c(j-1)+0.5c(j)
c(j-1) steps if the step moves up
c(j) steps if it moves left
2c(j)=2+c(j-1)+c(j)
c(j)=2+c(j-1)
or c(j)=2j
for p=0.1
c(j)=1+0.1c(j-1)+0.1c(j)
10c(j)=10+c(j-1)+c(j)
9c(j)=10+c(j-1)
c(j)=10/9 +c(j-1)/9
The expected #of steps at each level is 10/9
The time increases to perform find(x) operation
similarly for 0.9
c(j)=1+0.9c(j-1)+0.9c(j)
10 c(j)=10+9c(j-1)+9c(j)
c(j)=10+9c(j-1)
The expected time decreases with probability 0.9