O(n^2) is bad - can it be fixed?
roy at panix.com
Tue May 22 14:54:52 CEST 2001
"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 = 'foo'
for i in range(9000):
list[i] = ' '
would the list = 'foo' statement force enough memory to be
pre-allocated for the entire list, allowing the loop to run in linear time?
More information about the Python-list