• Jason House <jason.james.house gmail.com> Feb 14 2009
• Jason House <jason.james.house gmail.com> Feb 14 2009

Jason House <jason.james.house gmail.com> writes:

Andrei Alexandrescu 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.
 
 Andrei


Retrying when 90% full gives you a geometric series for the number of tries:
1+0.1+0.1^2+0.1^3+...
Ignoring the math trick to get 1/(1-p), it's easy to see it's 1.111111...
You're firmly in linear territory.

Jason House <jason.james.house gmail.com> writes:

Jason House Wrote:

 Andrei Alexandrescu 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.
 
 Andrei


 Retrying when 90% full gives you a geometric series for the number of tries:
1+0.1+0.1^2+0.1^3+...
 Ignoring the math trick to get 1/(1-p), it's easy to see it's 1.111111...
You're firmly in linear territory.


Ugh, I should not post when tired. p=0.9, not 0.1! 1/(1-0.9)=10. It's still
linear, but won't be as nice as my prior post implied. Sorry.