random cover of a range

[bearophile]

Andrei Alexandrescu:
> Say at some point there are k available (not taken) slots out of "n". 
> There is a k/n chance that a random selection finds an unoccupied slot. 
> The average number of random trials needed to find an unoccupied slot is 
> proportional to 1/(k/n) = n/k. So the total number of random trials to 
> span the entire array is quadratic. Multiplying that by 0.9 leaves it 
> quadratic.

It's like in hashing: if you want to fill 99% of the available space in a hash, then you take ages to find empty slots.
But if you fill it only at 75-90%, then on average you need only one or two tries to find an empty slot. So your time is linear, with a small multiplicative constant. When the slots start to get mostly full, you change algorithm, copying the empty slots elsewhere.

Bye,
bearophile