[Tutor] calling a variable name

[Ricardo Aráoz]

Kent Johnson wrote:
> Dave Kuhlman wrote:
>> On Tue, Oct 23, 2007 at 10:10:24PM -0400, Kent Johnson wrote:
>>
>> [snip]
>>
>>> Perhaps I was a bit hasty.
>>>
>>> Lists are implemented as arrays of references. I believe they are
>>> - amortized O(1) for append - occasionally the list must be reallocated 
>>> and copied
>> OK. I'm groping here.  Wikipedia tells me that O(1) means constant
>> increase.  So, what does "amortized O(1)" mean.
>>
>> My understanding is that appending in lists is optimized in the
>> sense that when more space is needed, Python allocates space for
>> additional elements so that allocation does not need to happen at
>> every append.  Here is a comment from the Python source code
>> (Python-2.5.1/Objects/listobject.c):
>>
>>     /* This over-allocates proportional to the list size, making room
>>      * for additional growth.  The over-allocation is mild, but is
>>      * enough to give linear-time amortized behavior over a long
>>      * sequence of appends() in the presence of a poorly-performing
>>      * system realloc().
>>      * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
>>      */
>>
>> Hmmm.  There is that "amortized" thing again.  Very suspicious. 
>> For a non-math and non-financial type like me, is it sort of like
>> saying that the costs are averaged out over a sequence of appends?
> 
> Yes, that is exactly right. Most of the time - when there is room at the 
> end of the allocated block - append is O(1) and very fast. Occasionally, 
> when there is not enough room, append is O(n) and slow, requiring the 
> entire list to be copied. Because the size of the new allocation is 
> proportional to the size of the list, the reallocation happens only each 
> 1/n appends, so if you average out the cost of the reallocation, each 
> append is O(1) (with a higher constant). That is what amortized cost 
> means - sometimes the cost is greater than the specified cost but it 
> averages out.
> 
> Note that if the reallocation added a fixed amount of extra space each 
> time the cost would not average out over n inserts and it would not be 
> O(1) amortized cost. It's important that the new allocation be 
> proportional to the existing space.
> 

Actually if you would come to the point you need to make a distinction
between amotized O(1) and O(1) then you will certainly be concerned with
the initial amount of allocation and with the proportional constant.