3.9 Analysis of Skip Lists

In a skiplist of 16 elements, we may have

• 9 elements at level 1
• 3 elements at level 2
• 3 elements at level 3
• 1 element at level 6

• One important question is:
  Where do we start our search? Analysis shows we should start from level L(n) where
  L(n) = log₂n
  In general if p is the probability fraction,
  L(n) = log_{${\frac{1}{p}}$}n
  where p is the fraction of the nodes with level i pointers which also have level (i + 1) pointers.

• However, starting at the highest level does not alter the efficiency in a significant way.

• Another important question to ask is:
  What should be MaxLevel? A good choice is
  MaxLevel = L(N) = log_{${\frac{1}{p}}$}N
  where N is an upperbound on the number of elements is a skiplist.

• Complexity of search, delete, insert is dominated by the time required to search for the appropriate element. This in turn is proportional to the length of the search path. This is determined by the pattern in which elements with different levels appear as we traverse the list.

• Insert and delete involve additional cost proportional to the level of the node being inserted or deleted.