Here is a simple code for a randomized skip-list:
Coin_Side flip()
{
if ( random() % 2 == 0 )
return HEADS;
else
return TAILS;
}
Note: random() returns an integer that uses a modulus of the form M = 2^B. Then, what is the expected performance of the skip list algorithm?
So we have: (ax mod M) mod 2 = (ax mod 2^B) mod 2 = (ax mod 2) mod 2^B
I can see than ((ax mod 2) == 0) will be true if ax is even. Then, by adding mod 2^B, we will skip more values in the skip-list. We would have only the even numbers that are multiples of 2^B. So would that make the algorithm better or worse?
