O(n^2) is bad - can it be fixed?

[Alex Martelli]

"Helen Dawson" <helend at accessone.com> wrote in message
news:3B0CAF2C.D744807A at accessone.com...
> Thanks for all the replies. I learned several tricks.
>
> However I find myself more worried than ever. I started out
> thinking that list was guaranteed to be O(n) for my problem,
> but now it appears that it isn't - it's dependent on good realloc
> behaviour. I think that's one thing the STL guys recognized
> well - incrementing by any (more or less) constant size
> can produce arbitrarily bad performance. A worst case
> memory penalty of 2x for doubling the size of list each time
> seems a fair price to pay for avoiding that

Just one more reflection... often you can get a sensible
estimate of how big your list will need to be, beforehand,
particularly if you're willing to tolerate a 'slop' of a
factor of 2 or so.  In this case, you can get substantially
better performance by "preallocating" the list rather than
using .append() on it.  If you wrap this into a UserList
subclass, or your own sequence object, it's not too hard
to keep client code blissfully unaware of the issue - it
calls .append() anyway, and the append method implementation
is the place where "the smarts" hide.

It's unlikely that you'll get an actual performance boost
from this approach, but you might get peace of mind:-).


Alex