About Skip List elements frequency

Question

First of all, I do not know very much about skip-lists, I am just trying to prepare for my exam. What is the frequency of the elements for optimal search (log(n)) on each level when having log(n) lists in a skiplist ? I know that when working with 2 lists, the first has n elements, and the second one has sqrt(n) elements. So, when searching for an element I do at most sqrt(n) steps on the second list (that above), and sqrt(n) steps in the first list (the one that contains all the elements) because the gaps between elements are sqrt(n)-long. So that seems ok. But how many elements does each list have when working with log(n) lists ?

Answer 1

When an element is added to a skip list "a coin is flipped" several times to decide in how many layers the new element should be included. The element is always added to the first (lowest) layer and then added to the next layer above each time the coin lands on heads. If we call the probability of getting heads in a coin flip p (commonly p = 0.5 is used), each element is added with probability 1 to the first layer, with probability p to the second layer, with probability p^2 to the third layer and in general with probability p^(i-1) to the i-th layer. If the skip list contains n elements, the second layer contains n*p elements in expectation (not sqrt(n)), the third layer n*p^2 elements and in general the i-th layer n*p^(i-1) elements. For example, in a skip list with p = 0.5 and n = 64 elements we would expect the second layer to contain about 32 elements, the third about 16 and so on, and we would thus expect to have about log_(1/p)(n) = log_2(n) layers in total. To search an element in a skip list, we first linearly scan the topmost list (which contains only a few elements, maybe 2 or 3). This allows us to restrict our search to a smaller range in the list below. We then scan that range of the list below and repeat the process until we reach the bottommost list. With p = 0.5 you can almost think of it as a binary search. For example, with n = 64 elements we would expect to take about 2 steps of about 32 elements in the topmost list, restricting our search in the list below to a range of about 32 elements. We would then scan these 32 elements in the list below at steps of about 16 elements, and so on.