• Jerry Quinn <jlquinn optonline.net> Feb 14 2009

Jerry Quinn <jlquinn optonline.net> writes:

Andrei Alexandrescu Wrote:

 Bill Baxter wrote:
 On Sat, Feb 14, 2009 at 1:03 PM, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail 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