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.
