Proving Skip List probability

314 views Asked by At

How can I prove that, with a Skip List variant of nodes deciding their height by throwing a six-sided (If the die takes any of the values 2 through 6, then the node promotes itself to the next level. The node finalizes its level when the die roll is 1.), if there are n nodes then the number of lists O(log n) with probability at least 1 − 1/n (show that the probability any node is in at most c*logn levels, where c, some constant, is >= 1 - 1/n)

0

There are 0 answers