On Fri, Feb 13, 2009 at 7:21 AM, Andrei Alexandrescu <[email protected]> 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
