Arrays/Python/AppendCost

Ammortized Cost of Appending is O(1)

The following script shows that the amortized cost of expanding when appending to a list is O(1) when amortized over the operations where the resizing operation is not performed.

The script prints the amount of time per operation for appending None objects to a list. These show the amortized cost of resizing an array dynamically is independent of the array size, and is therefore O(1).

The output

$ python amortized-append-cost.py
n:       10	microsec: 0.501
n:      100	microsec: 0.131
n:     1000	microsec: 0.150
n:    10000	microsec: 0.107
n:   100000	microsec: 0.106
n:  1000000	microsec: 0.124
n: 10000000	microsec: 0.110

The script

git.charlesreid1.com repo

https://charlesreid1.com:3000/cs/python/src/master/arrays/amortized-append-cost.py

source

"""
Goodrich et al
Data Structures in Python
Chapter 5: Array-Based Sequences

Demonstrate the amortized cost of resizing when append happens.

Much to learn: https://docs.python.org/3/library/string.html#formatstrings
"""

from time import time, clock

def compute_average(n):
    data = []
    start = time()
    startc = clock()
    for k in range(n):
        data.append(None)
    end = time()
    endc = clock()
    return (end-start)/n
    #return ((end-start)/n, (endc-startc)/n)

if __name__=="__main__":
    values = [int(10**j) for j in range(1,8)]
    for n in values:
        INV_MICROSEC = 10**6
        t = compute_average(n)*INV_MICROSEC
        print("n: {0:10d}\tmicrosec: {1:.3f}".format(n,t))