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_{2}*n**p*is the probability fraction,*L*(*n*) = log_{}*n**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_{}*N**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.