random cover of a range

[Andrei Alexandrescu]

bearophile wrote:
> Andrei Alexandrescu:
>> I understood that. My problem is that a quadratic algorithm is applied 
>> to 0.9 of the input. That makes overall behavior quadratic even if you 
>> complete the last 10% in no time.
> 
> No part of the algorithm I have shown is quadratic, I think.

Your algo is:

=========
- create an array of m bits, set to zero
- Use a random generator to generate integer numbers in [0, m-1], if the 
corresponding big is set, extract another random number, if it's not set 
then set it, increment a counter, and return the array item that 
corresponds to the bit.
- When about 90% of the bits is set, [... alternate impl ...]
==========

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.


Andrei