Surprising (for me) benchmark results...

[Courageous]

>If you want to consider things that way then you have to worry
>about Python's list extension, which last I heard was O(N**2)...

NO.

list.append() appends items to a dynamic array in O(1)+k
constant amortized time. It does this by using a liberal preallocation
strategy, and leaving empty slots into which new elements can
be placed. The occasional realloc() amortizes away quite readily.

C//