On Mon, May 7, 2012 at 3:52 PM, Cameron Simpson <c...@zip.com.au> wrote: > | (or add 50% or something) each > | time, meaning that as n increases, the frequency of reallocations > | decreases - hence the O(1) amortized time. > > Hmm, yes. But it is only O(1) for doubling. If one went with a smaller > increment (to waste less space in the end case where one stops growing the > array) then there are more copies and less .append efficiency, trading > potential memory bloat for compute time in .append(). If you went all > the way to adding only one item the cost goes to O(n) for .append() > and O(n^2) overall, with varying costs in between.
It's O(1) amortized as long as the increment is exponential. IIRC Python actually grows the list by a factor of 1/8 in the limit, which is still exponential and still O(1) amortized. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
