<div class="gmail_quote">On Sat, Feb 14, 2009 at 1:17 PM, Bill Baxter <span dir="ltr"><<a href="mailto:wbaxter@gmail.com">wbaxter@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="gmail_quote"><div><div></div><div class="Wj3C7c">On Sat, Feb 14, 2009 at 1:03 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org" target="_blank">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><div></div><div>bearophile wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Andrei Alexandrescu:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Say at some point there are k available (not taken) slots out of<br>
"n". There is a k/n chance that a random selection finds an<br>
unoccupied slot. The average number of random trials needed to find<br>
an unoccupied slot is proportional to 1/(k/n) = n/k. So the total<br>
number of random trials to span the entire array is quadratic.<br>
Multiplying that by 0.9 leaves it quadratic.<br>
</blockquote>
<br>
It's like in hashing: if you want to fill 99% of the available space<br>
in a hash, then you take ages to find empty slots. But if you fill it<br>
only at 75-90%, then on average you need only one or two tries to<br>
find an empty slot. So your time is linear, with a small<br>
multiplicative constant. When the slots start to get mostly full, you<br>
change algorithm, copying the empty slots elsewhere.<br>
</blockquote>
<br></div></div>
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.</blockquote>
<div> </div></div></div><div>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 he stops when that reaches a maximum of 9 then the algo can't be quadratic up to that point. It's O(n) expected, with a possibly fairly high hidden constant. It also has a fairly long tail, as in there's a small probability of it taking a very long time to complete.<br>
</div></div></blockquote><div><br>... the real gotcha is that he's using O(n) extra memory. 10% of n is still O(n) memory for shuffling the last 10% of the items.<br><br><br>--bb <br></div></div>