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

[Aahz Maruch]

In article <3B0CAF2C.D744807A at accessone.com>,
Helen Dawson  <helend at accessone.com> wrote:
>
>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 (especially since you
>can make the memory penalty arbitrarily small - any ratio above one is
>theoretically equivalent). Oh well.

What you're saying is theoretically true.  In practice, very few people
run into the non-O(n) nature of lists, because the constant factor for
expansion is large enough and other operations tend to swamp the list
resize time.
-- 
                      --- Aahz  <*>  (Copyright 2001 by aahz at pobox.com)

Androgynous poly kinky vanilla queer het Pythonista   http://www.rahul.net/aahz/
Hugs and backrubs -- I break Rule 6

"You do not make history; you can only hope to survive it."  --G'kar