random cover of a range

[Steve Schveighoffer]

On Fri, 13 Feb 2009 16:45:21 -0800, Andrei Alexandrescu wrote:

> Steven Schveighoffer wrote:
>> Average runtime is still going to be O(n^2), because the average
>> element chosen should be k / 2 elements into the range.
> 
> So at some point there are k slots for grabs out of n. The number of
> steps taken is composed of some steps taken because of the already-taken
> slots, plus the number of steps taken because the dice tells me to
> ignore the slot even if it could be taken. The first number of steps is
> proportional to the number of taken slots, i.e. n-k. The second number
> of steps is proportional to the number of options, i.e. k. If you sum
> you get indeed O(n) per pass.
> 
> Now let us consider the following improvement: whenever an element at
> the front of the array is taken, we eliminate all elements in the front
> that were taken already. That way there's no more need to skip each time
> over already-occupied slots. In other words, it is an invariant that the
> first slot we'll look at is not taken. How does this affect complexity?

It does not affect the complexity.  It is an optimization, but one that 
is proportional to n because k is proportional to n, so it gets factored 
out, and still becomes O(n).

even if you removed the used elements so they are not traversed, you 
still get O(n^2) because of the linear search.

-Steve