( exp (nworst-case ( skip lists an interesting data structure for efficiently realizing the dictionary adt is the skip list this data structure makes random choices in arranging the entries in such way that search and update times are (lognon averagewhere is the number of entries in the dictionary 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 entry the running time is averaged over all possible outcomes of the random numbers used when inserting entries because they are used extensively in computer gamescryptographyand computer simulationsmethods that generate numbers that can be viewed as random numbers are built into most modern computers some methodscalled pseudorandom number generatorsgenerate random-like numbers deterministicallystarting with an initial number called seed 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 methods that result are usually simple and efficient we can devise simple randomized data structurecalled the skip listwhich has the same logarithmic time bounds for searching as is achieved by the binary searching algorithm neverthelessthe bounds are expected for the skip listwhile they are worst-case bounds for binary searching in look-up table on the other handskip lists are much faster than look-up tables for dictionary updates skip list for dictionary consists of series of lists { each list stores subset of the entries of sorted by nondecreasing key plus entries with two special keysdenoted and +where is smaller than every possible key that can be inserted in and is larger than every possible key that can be inserted in in additionthe lists in satisfy the followinglist contains every entry of dictionary (plus the special entries with keys and +for list contains (in addition to and + randomly generated subset of the entries in list - list contains only and