## 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

Repo on git.charlesreid1.com: https://git.charlesreid1.com/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))

```