[Scummvm-devel] ScummVM 1.0.0: Release status 2009-08-11 -- Full feature, freeze

[Marcus Comstedt]

Kostas Nakos <knakos at phys.uoa.gr> writes:

> Well, it is a good, in theoretical treatment terms, strategy to double 
> the size of a dynamic table on overflow and halve it when the number of 
> elements drops below a quarter. This keeps an asymptotic O(N) for a 
> sequence of N insert/deletes.

Actually, it is not necessary to double the size to get this
asymptotic O, you just need to make the new size a multiple of the old
size.  So a multiple of 1.5 or 1.2 (making the array 50% or 20%
larger) works as well as one of 2.  (Which is to say, the O is the
same, but the constant increases a bit.)


  // Marcus