Andrei Alexandrescu Wrote: > Bill Baxter wrote: > > On Sat, Feb 14, 2009 at 1:03 PM, Andrei Alexandrescu > > <seewebsiteforem...@erdani.org <mailto:seewebsiteforem...@erdani.org>> > > wrote: > > > > bearophile wrote: > > > > Andrei Alexandrescu: > > > > Say at some point there are k available (not taken) slots out of > > "n". There is a k/n chance that a random selection finds an > > unoccupied slot. The average number of random trials needed > > to find > > an unoccupied slot is proportional to 1/(k/n) = n/k. So the > > total > > number of random trials to span the entire array is quadratic. > > Multiplying that by 0.9 leaves it quadratic. > > > > > > It's like in hashing: if you want to fill 99% of the available space > > in a hash, then you take ages to find empty slots. But if you > > fill it > > only at 75-90%, then on average you need only one or two tries to > > find an empty slot. So your time is linear, with a small > > multiplicative constant. When the slots start to get mostly > > full, you > > change algorithm, copying the empty slots elsewhere. > > > > > > Well I don't buy it. If you make a point, you need to be more > > precise than such hand-waving. It's not like in hashing. It's like > > in the algorithm we discuss. If you make a clear point that your > > performance is better than O(n*n) by stopping at 90% then make it. I > > didn't go through much formalism, but my napkin says you're firmly > > in quadratic territory. > > > > > > Well he has a point that the number of trials required to find an empty > > depends not on the absolute number of empty items, but only the ratio of > > empties to fulls. Even your own claim about average number of trials > > was n/k -- not sure how you got that though. > > If you toss a N-side dice hoping for a specific face to show up (and > stopping afterwards), how many times do you have to toss it on average? > I recall (without being sure) that you need to toss it a number of times > proportional to N. Could anyone confirm or deny?
avg_trials(N) = sum(t = 1-inf) { 1/N * ((N-1)/N)^(t-1) } where t is the number of trials. Experimentally, it converges to N