array, list, performance...

[Tim Peters]

[Michael Chermside]
>     li = [x0, x1, x2, ...]
> ...
>     li.append(x)   appending is O(1)
>                    (actually, it SOMETIMES takes O(len(li)) as it
>                     resizes the list. But if you grow a list by
>                     continually appending, the amortized time is
>                     linear (ie, constant amortized time per element)

[Ype Kingma]
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).

For Python 2.2 Michael is correct.  For Python 2.1 and earlier, you're
correct "in theory", although in practice it was often linear-time anyway,
depending on internal details of the platform realloc.

> You can prevent that by creating a list a large enough list
> when starting, eg:
>
> li = [None] * neededSize

Yup, and that can save time regardless.