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
