mardi 16 juin 2015

Proving Skip List probability

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 is some constant, is >= 1 - 1/n)




Aucun commentaire:

Enregistrer un commentaire