mapshash tablesand skip lists and place that item in si+ if the coin comes up "heads thuswe expect to have about / itemss to have about / itemsandin generalsi to have about / items in other wordswe expect the height of to be about log the halving of the number of items from one list to the next is not enforced as an explicit property of skip listshowever insteadrandomization is used functions that generate numbers that can be viewed as random numbers are built into most modern computersbecause they are used extensively in computer gamescryptographyand computer simulationssome functionscalled pseudorandom number generatorsgenerate random-like numbersstarting with an initial seed (see discusion of random module in section other methods use hardware devices to extract "truerandom numbers from nature in any casewe will assume that our computer has access to numbers that are sufficiently random for our analysis the main advantage of using randomization in data structure and algorithm design is that the structures and functions that result are usually simple and efficient the skip list has the same logarithmic time bounds for searching as is achieved by the binary search algorithmyet it extends that performance to update methods when inserting or deleting items neverthelessthe bounds are expected for the skip listwhile binary search has worst-case bound with sorted table skip list makes random choices in arranging its structure in such way that search and update times are (log non averagewhere is the number of items in the map interestinglythe notion of average time complexity used here does not depend on the probability distribution of the keys in the input insteadit depends on the use of random-number generator in the implementation of the insertions to help decide where to place the new item the running time is averaged over all possible outcomes of the random numbers used when inserting entries using the position abstraction used for lists and treeswe view skip list as two-dimensional collection of positions arranged horizontally into levels and vertically into towers each level is list si and each tower contains positions storing the same item across consecutive lists the positions in skip list can be traversed using the following operationsnext( )return the position following on the same level prev( )return the position preceding on the same level below( )return the position below in the same tower above( )return the position above in the same tower we conventionally assume that the above operations return none if the position requested does not exist without going into the detailswe note that we can easily implement skip list by means of linked structure such that the individual traversal methods each take ( timegiven skip-list position such linked structure is essentially collection of doubly linked lists aligned at towerswhich are also doubly linked lists