Page "Skip list" Paragraph 28

The following proves these two claims concerning the advantages of quasi-randomness over the totally derandomized version.

First, to prove that the search time is guaranteed to be logarithmic.

Suppose a node n is searched for, where n is the position of the found node among the nodes of level 1 or higher.

If n is even, then there is a 50 / 50 chance that it is higher than level 1.

However, if it is not higher than level 1 then node n-1 is guaranteed to be higher than level 1.

If n is odd, then there is a 50 / 50 chance that it is higher than level 1.

Suppose that it is not ; there is a 50 / 50 chance that node n-1 is higher than level 1.

Suppose that this is not either ; we are guaranteed that node n-2 is higher than level 1.

The analysis can then be repeated for nodes of level 2 or higher, level 3 or higher, etc.

always keeping in mind that n is the position of the node among the ones of level k or higher for integer k. So the search time is constant in the best case ( if the found node is the highest possible level ) and 2 times the worst case for the search time for the totally derandomized skip-list ( because we have to keep moving left twice rather than keep moving left once ).