random cover of a range

[Bill Baxter]

On Fri, Feb 13, 2009 at 7:21 AM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:
> Jason House wrote:
>>
>> Andrei Alexandrescu Wrote:
>
>> No.  Your wording sounds like you're doing
>> stuff that's way off, but the resulting math is correct.  My
>> calculation would be based on the average length of a sequence of 1's
>> (k/(n-k)).  That means the work is 1+k/(n-k) = n/(n-k).
>
> Well my wording means this: in an array of length n with k "holes"
> randomly distributed, the probability one slot is a a no-hole is
> (n-k)/n. What we want is to find the first no-hole starting from a
> random position in the array. How many steps do we do on average? That
> is the same as the average number of steps of rolling a fair dice with
> (n-k) faces until we obtain a particular face. And the average number of
> steps is IIRC 1/p = n/(n-k).

Except your holes aren't randomly distributed, because you are more
likely to fill a hole next to an already filled slot.
Not sure how badly that skews the big-oh though.   Sounds like a
problem you'd find the answer to in an advanced text covering hashing,
because it sounds just like hashing with linear probing.

--bb