howeversince the probability of having fair coin repeatedly come up heads forever is moreoverwe cannot infinitely add positions to list without eventually running out of memory in any caseif we terminate position insertion at the highest level hthen the worst-case running time for performing the findinsertand remove operations in skip list with entries and height is ( hthis worst-case performance occurs when the tower of every entry reaches level - where is the height of howeverthis event has very low probability judging from this worst casewe might conclude that the skip list structure is strictly inferior to the other dictionary implementations discussed earlier in this but this would not be fair analysisfor this worst-case behavior is gross overestimate bounding the height of skip list because the insertion step involves randomizationa more accurate analysis of skip lists involves bit of probability at firstthis might seem like major undertakingfor complete and thorough probabilistic analysis could require deep mathematics (andindeedthere are several such deep analyses that have appeared in data structures research literaturefortunatelysuch an analysis is not necessary to understand the expected asymptotic behavior of skip lists the informal and intuitive probabilistic analysis we give below uses only basic concepts of probability theory let us begin by determining the expected value of the height of skip list with entries (assuming that we do not terminate insertions earlythe probability that given entry has tower of height > is equal to the probability of getting consecutive heads when flipping cointhat isthis probability is / hencethe probability pi that level has at least one position is at most < / ifor the probability that any one of different events occurs is at most the sum of the probabilities that each occurs the probability that the height of is larger than is equal to the probability that level has at least one positionthat isit is no more than this means that is larger thansay log with probability at most log < / log / / for exampleif this probability is one-in- -million long shot more generallygiven constant is larger than log with probability at most /nc- that isthe probability that is smaller than log is at least /nc- thuswith high probabilitythe height of is (logn