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
