sorting 1172026 entries

[Ian Kelly]

On Mon, May 7, 2012 at 3:52 PM, Cameron Simpson <cs at 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