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

[alex]

David Cournapeau wrote:
> On Mon, Jan 26, 2009 at 11:52 PM, Sturla Molden <sturla at molden.no> wrote:
>   
>>> Sturla Molden wrote:
>>>       
>>> This is independent of the list implementation, isn't it ? I am quite
>>> curious to understand how you could get O(1) complexity for a "growable"
>>> container: if you don't know in advance the number of items, and you add
>>> O(N) items, how come you can get O(1) complexity ?
>>>       
>> Each time the array is re-sized, you add in some extra empty slots. Make
>> sure the number of extra slots is proportional to the size of the array.
>>     
>
> So this is the well known method of over allocating when you need to
> grow, right ? This is not constant time, and depends on the number of
> items you are adding I think (sublinearly, but still)
>
>   
I think you guys are talking about different N.  If N is the number of 
items already in the list, then adding a single item to the list could 
be O(N) if you use arrays to represent lists and you do not 
over-allocate when you need to grow.  By over-allocating when you need 
to grow, you can get amortized O(1) for the operation of adding a single 
element (not N elements) to the list.  Python apparently uses this 
latter method.  I guess the discussion started on the topic of the 
difference between arrays and lists, and that Python's 'list' has some 
properties of a classical 'array' (fast random access) and some of a 
classical 'list' (fast amortized append).

Alex