random cover of a range

[bearophile]

Christopher Wright:
> Agreed. Worst-case quadratic can perform much better in many 
> circumstances, and the proposed algorithm is tunable.

I think it's not quadratic :-) (See the answer by Bill B.)


> 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.

There are some variants of that algorithm designed to be recursive, like you say. I have tried them, and they are slower, etc. That's why I have shown here the simpler version. Sometimes more complex algorithms aren't better.

Bye,
bearophile