figure before and after an insertion proceed as in searchand keep track of each point where we switch to lower level the new nodewhose level is determined randomlyis then spliced into the list this operation is shown in figure cursory analysis shows that since the expected number of nodes at each level is unchanged from the original (nonrandomizedalgorithmthe total amount of work that is expected to be performed traversing to nodes on the same level is unchanged this tells us that these operations have (log nexpected costs of coursea more formal proof is requiredbut it is not much different from this skip lists are similar to hash tablesin that they require an estimate of the number of elements that will be in the list (so that the number of levels can be determinedif an estimate is not availablewe can assume large number or use technique similar to rehashing experiments have shown that skip lists are as efficient as many balanced search tree implementations and are certainly much simpler to implement in many languages skip lists also have efficient concurrent implementationsunlike balanced binary search trees hence they are provided in the java librarythough not yet in +primality testing in this sectionwe examine the problem of determining whether or not large number is prime as was mentioned at the end of some cryptography schemes depend on the difficulty of factoring large -digit number into two -digit primes in order to implement this schemewe need method of generating these two primes if is the number of digits in nthe obviousmethod of testing for the divisibility by odd numbers from to requires roughly divisionswhich is about / and is completely impractical for -digit numbers in this sectionwe will give polynomial-time algorithm that can test for primality if the algorithm declares that the number is not primewe can be certain that the number is not prime if the algorithm declares that the number is primethenwith high probability but not percent certaintythe number is prime the error probability does not depend on the particular number that is being tested but instead depends on random choices made