> 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//


-- 
http://mail.python.org/mailman/listinfo/python-list