random cover of a range

[Christopher Wright]

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.

Or as an alternative, when you have hit (say) half the elements, you 
copy over the remaining elements and repeat. This gives you an amortized 
O(n log n) algorithm, with O(n log n) allocated memory.

> Bye,
> bearophile