random cover of a range

[Andrei Alexandrescu]

Christopher Wright wrote:
> bearophile wrote:
>> Andrei Alexandrescu:
>>> Your handwaving ain't much better than my memory. Hey, either 
>>> somebody goes through the math over here or we can give up on the 
>>> whole thing and use O(n) storage for the blessed thing.<
>>
>> We can implement both, and we can look what's better in practical 
>> situations.
> 
> Agreed. Worst-case quadratic can perform much better in many 
> circumstances, and the proposed algorithm is tunable.

I think if we want to look like professionals we're not going to do 
that. History of computing is full of embarrassing quadratic algorithms 
failing miserably when advances in storage capacity or simply data set 
growth within the original program showed their pernicious tendencies. I 
have authored such a program when I was a student :o).


Andrei