so we have yet to bound the number of scan-forward steps we make let ni 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 ni is / thereforethe expected value of ni 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 (log nlevels with high probabilitya search in takes expected time (log nby similar analysiswe can show that the expected running time of an insertion or removal is (log nspace 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 + - + = hencethe expected space requirement of is (ntable summarizes the performance of sorted map realized by skip list operation len(mk in [kv del [km find min) find maxm find lt( ) find gt(km find le( ) find ge(km find range(startstopiter( )reversed(mrunning time ( (log nexpected (log nexpected (log nexpected ( (log nexpected ( log nexpectedwith items reported (ntable performance of sorted map implemented with skip list we use to denote the number of entries in the dictionary at the time the operation is performed the expected space requirement is (