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

[Ben Hutchings]

Isaac To Kar Keung <kkto at csis.hku.hk> writes:
<snip>
> That means, when size is below 500, a list size will always be multiple of
> 10.  When size is larger, it is always multiple of 100.  Of course, if the
> object is already of the right size, the system resize() does nothing.
> 
> Seems like magic to me... I run the following program and I didn't see *any*
> slowdown, when each of the lists is as large as 8M, eating up 60M memory...
<snip>
> (Will it be the system realloc which actually do the geometric scaling, or
> is it really that geometric scaling is unnecessary?)

As the list buffer grows, realloc() will at some point find that the
only place to put it is at the top of the heap.  Once it's there,
further realloc() calls will grow the heap and will not need to move
the buffer.  However, other systems - those with a shared memory
space, or without a smart implementation of realloc() - are likely to
behave differently.

-- 
Any opinions expressed are my own and not necessarily those of Roundpoint.