[SciPy-user] How to start with SciPy and NumPy
Mon Jan 26 10:34:21 CST 2009
On Tue, Jan 27, 2009 at 1:16 AM, Sturla Molden <firstname.lastname@example.org> wrote:
>> 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.
Ok - I did not understand what amortized cost meant.
> By the way, a Python list does not double in size on each allocation. It
> has a less greedy growth pattern.
Yes - but then python does not use malloc directly either anyway :)
More information about the SciPy-user