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

[Courageous]

On Fri, 25 May 2001 05:25:50 GMT, Helen Dawson <helend at accessone.com> wrote:

>The current behaviour is to add 10 items initially, and then
>switch to adding 100 items. This strikes me as being a weak
>approximation to proper geometric expansion, and I'm not sure
>what the benefit's are. Increasing by some fraction of the
>current size would be much more reliable.

And furthermore, using a 100% growth factor enables a provably*
O(1)+k amortized append time. If you don't like the Python list,
use my "dlist" at http://www.sourceforge.net/projects/pythonic.
While it's incomplete (no sorting, for example), it has favorable
growth factors, with the addition of simulateously supporting
O(1) insert-at-head, O(1)+k append-at-tail, and O(1) random
access. It's a bit of a memory hog because of the allocation
strategy it uses to achieve the fast head and tail performance.

It is *only* available by anonymous cvs at the moment. Follow
the links to cvs, and check out the "pythonic" cvs module.
Then compile the adt submodule and read the test_dlist.py
source example.

If you have any more questions, contact me by email.

C//

*beyond my math skills, but so I've been told.