Amortized analysis: Insertion in a list

[quazirfan]

I am trying to calculate the time is takes to append one element in a list. According to amortized analysis, it should be constant regardless how long the list is.

So, here is a little piece of code I've written to test it out with the corresponding output,

def calTime(n): from time import time data = [] start = time() for r in range(n): data.append(None) end = time() return ((end - start)/n) for r in [10**x for x in range(15)]: print("Size ",r, " time it took ", calTime(r), "sec")

Output:

Input is being redirected from C:\Projects\2698\input.txt Size 1 time it took 0.0 sec Size 10 time it took 0.0 sec Size 100 time it took 0.0 sec Size 1000 time it took 0.0 sec Size 10000 time it took 1.0018348693847657e-07 sec Size 100000 time it took 1.099705696105957e-07 sec Size 1000000 time it took 8.603405952453613e-08 sec Size 10000000 time it took 8.960003852844239e-08 sec

I have two questions,

1. Is this the correct way to test if amortized cost of insertion in a dynamic array is O(1) - I am assuming it is correct as average insertion time for all values or n are very close to zero.
   
2. I understand that the average time it takes to insert an elements in a list when n is small being rounded to zero. How do I print that small value?
   

[deanhystad]

It is not a rounding problem. It is a timer problem. Your timer mas a smallest minimum time it can measure. Periods less than that may appear to be zero time.