maintaining the topmost level skip list must maintain reference to the start position (the topmostleft position in sas an instance variableand must have policy for any insertion that wishes to continue inserting new entry past the top level of there are two possible courses of action we can takeboth of which have their merits one possibility is to restrict the top levelhto be kept at some fixed value that is function of nthe number of entries currently in the map (from the analysis we will see that max{ log is reasonable choiceand picking log nis even saferimplementing this choice means that we must modify the insertion algorithm to stop inserting new position once we reach the topmost level (unless log nlog( )in which case we can now go at least one more levelsince the bound on the height is increasingthe other possibility is to let an insertion continue inserting new position as long as heads keeps getting returned from the random number generator this is the approach taken by algorithm skipinsert of code fragment as we show in the analysis of skip liststhe probability that an insertion will go to level that is more than (log nis very lowso this design choice should also work either choice will still result in the expected (log ntime to perform searchinsertionand removalhoweverwhich we show in the next section probabilistic analysis of skip lists as we have shown aboveskip lists provide simple implementation of sorted map in terms of worst-case performancehoweverskip lists are not superior data structure in factif we do not officially prevent an insertion from continuing significantly past the current highest levelthen the insertion algorithm can go into what is almost an infinite loop (it is not actually an infinite loophoweversince 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 worstcase running time for performing the getitem setitem and delitem map operations in skip list with entries and height is ( hthis worstcase 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 map implementations discussed earlier in this but this would not be fair analysisfor this worst-case behavior is gross overestimate