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

[Roy Smith]

"Alex Martelli" <aleaxit at yahoo.com> wrote:
> Not quite -- Python's sources are pretty clear about that:-).  A
> list DOES allocate a few extra entries when it grows, but it does
> NOT grow geometrically.  So IN THEORY appending should be O(N^2)
> for lists as well -- but in practice it seems N never gets big
> enough to actually measure that effect.

How does python deal with sparse lists, i.e. what if I did this:

list = []
list[9001] = 'foo'
for i in range(9000):
   list[i] = ' '
del list[9001]

would the list[9001] = 'foo' statement force enough memory to be 
pre-allocated for the entire list, allowing the loop to run in linear time?