[SciPy-user] How to start with SciPy and NumPy
Mon Jan 26 10:16:39 CST 2009
> On Tue, Jan 27, 2009 at 12:32 AM, alex <email@example.com> 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.
More information about the SciPy-user