[Tutor] calling a variable name

[Kent Johnson]

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.

Kent