random cover of a range

[Andrei Alexandrescu]

Bill Baxter wrote:
> On Sat, Feb 14, 2009 at 2:20 PM, Andrei Alexandrescu
> The probability of *not* getting the number after t tries is
> (1-1/n)^t, so it's just a pure decaying exponential, the chance of
> getting it after t tries should be 1 minus that.  The average number
> of tries is going to be some kind of integral of that curve, and an
> integral of an exponential is still an exponential, so it seems
> unlikely to me that your memory was correct on this one.

Thanks for finding the pdf with the calculation. It looks like this old 
brain can still remember something :o).

>> Now, assuming the above is true, say we decide to do the linear search for a
>> fraction f of the n elements in the array.
> 
> Maybe you were switching subjects (to your algorithm?) here, but just
> to be clear, Bearophile didn't say anything about doing a linear
> search.  His first phase is just to do repeated dart-throwing trials
> till an empty is found.

I meant random trials. What I was saying was that it takes linear time 
to hit an element.

>> . The average number of steps will
>> be:
>>
>> S = n * (1/n + 1/(n - 1) + 1/(n - 2) + ... + 1/(n - fn))
>>
>> So we're looking for the harmonic series that does not start from 1, but
>> instead starts from its fn'th term (you drop the first (1-f)n terms). Does
>> it converge? (I don't know.)
> 
> In the limit of what?  You seem to be asking if a finite series converges.

S is the average number of steps taken to finishing the task. I'm 
looking for a bound on that number of steps. With the clear Saturday 
morning outlook, it seems that it's in any case better than O(n log n), 
which means that bearophile was right - it's not quadratic. But I've 
been wrong a number of times on this because I keep on trying to 
convince someone else to do the math, so someone please confirm :o).

Andrei