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 (lognwith high probabilitythe number of drop-down steps is (lognwith high probability so we have yet to bound the number of scan-forward steps we make let be the number of keys examined while scanning forward at level observe thatafter the key at the starting positioneach additional key examined in scan-forward at level cannot also belong to level + if any of these keys were on the previous levelwe would have encountered them in the previous scan-forward step thusthe probability that any key is counted in is / thereforethe expected value of is exactly equal to the expected number of times we must flip fair coin before it comes up heads this expected value is hencethe expected amount of time spent scanning forward at any level is ( since has (lognlevels with high probabilitya search in takes expected time (lognby similar analysiswe can show that the expected running time of an insertion or removal is (lognspace usage in skip list finallylet us turn to the space requirement of skip list with entries as we observed abovethe expected number of positions at level is / which means that the expected total number of positions in is using proposition on geometric summationswe have for all > hencethe expected space requirement of is (ntable summarizes the performance of dictionary realized by skip list table performance of dictionary implemented with skip list we denote the number