random cover of a range

[Andrei Alexandrescu]

bearophile wrote:
> 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.

Well I don't buy it. If you make a point, you need to be more precise 
than such hand-waving. It's not like in hashing. It's like in the 
algorithm we discuss. If you make a clear point that your performance is 
better than O(n*n) by stopping at 90% then make it. I didn't go through 
much formalism, but my napkin says you're firmly in quadratic territory.

Andrei