pop(i) is O(k) not O(n)

[irunestone]

Error reported in course FIT5211 on page Lists by user lwoo0004 lindy.woodburn@gmail.com Incorrect info on page ... pop(i) is O(k) not O(n). e.g. popping from an indexed location from the end of a list

See python docs: https://wiki.python.org/moin/TimeComplexity Pop intermediate O(k)

And revised code:

popzero = timeit.Timer("x.pop(0)", "from main import x") popend = timeit.Timer("x.pop()", "from main import x") popend_minus = timeit.Timer("x.pop(-2)", "from main import x") . # ADDED

print("pop(0) pop() pop(-2)") for i in range(1000000,100000001,1000000): x = list(range(i)) pt = popend.timeit(number=1000) x = list(range(i)) pz = popzero.timeit(number=1000) x = list(range(i)) pe = popend_minus.timeit(number=1000) print("%15.5f, %15.5f, %15.5f" %(pz,pt,pe)) pop(0) pop() pop(-2) 0.40309, 0.00010, 0.00015 1.20204, 0.00009, 0.00017 1.93542, 0.00009, 0.00014 2.73203, 0.00009, 0.00014 3.45721, 0.00010, 0.00015 4.21476, 0.00011, 0.00015 5.14111, 0.00010, 0.00017

[bnmnetp]

The wiki is reporting Average times and Amortized times, not worst case times.