[SciPy-user] How to start with SciPy and NumPy

[Sturla Molden]

> On Tue, Jan 27, 2009 at 12:32 AM, alex <argriffi at ncsu.edu> wrote:

> I meant that adding N items to a list requires O(log(N)) malloc when
> using over allocation (double the size at ever allocation). I am not
> sure to understand how the number of items already in the list would
> influence the complexity of growing, at least when complexity =
> counting the number of malloc.

Because the items already in the list has to be copied for every malloc.
The O(log(N)) mallocs do not have O(1) complexity. The complexity is not
counting the number of mallocs.

By the way, a Python list does not double in size on each allocation. It
has a less greedy growth pattern.


S.M.