Andrei Alexandrescu 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). > > > Given that O(n*log(n)) is the theoretical best you can do, having a > > result that is < O(n*log(n)) is highly suspect. The sum 1/1 + 1/2 + > > 1/3 + 1/4 + 1/5 + ... is in fact O(log(n)). > > Ever so pedantic. :o) I meant "<=" because I wasn't aware of the best > theoretical bound. Do you have a pointer? Thanks.
I was thinking of the theoretical bound on sorting being n*log(n) but that does not apply in this case. The bound on sum(1/x) is pretty simple. The discrete sampling of 1/n can be made into either an over or under approximation of the integral depending on how you shift the starting points. That means sum(1/x) = ln(n)+C, where is 0 < C < 1 > I have the feeling there is something clever to do after half of the > array was covered. After that, the probability of a random element being > uncovered falls below 0.5. > > I also have the feeling that interesting things can be done if the > length of the range has certain values, such as the period of certain > generators with certain parameters. I don't have the time to look into > that now. Anyone versed in e.g. linear congruential generators with a > given period? > > One way or another, I'll add RandomCover to std.random. Thanks Leonardo, > Denis, Steve, and Jason. > > > Andrei
