mapshash tablesand skip lists 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 pi < for 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 pi 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 (log nanalyzing search time in skip list nextconsider the running time of search in skip list sand recall that such search involves two nested while loops the inner loop performs scan forward on level of as long as the next key is no greater than the search key kand the outer loop drops down to the next level and repeats the scan forward iteration since the height of is (log nwith high probabilitythe number of drop-down steps is (log nwith high probability