[List] Big-O Efficiency of Python List

1. Big-O Efficiency of Python List Operators

 

Operation	Big-O Efficiency
index []	O(1)
index assignment	O(1)
append	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i, item)	O(n)
del operator	O(n)
iteration	O(n)
contains (in)	O(n)
get slice [x:y]	O(k)
del slice	O(n)
set slice	O(n+k)
reverse	O(n)
concatenate	O(k)
sort	O(nlogn)
multiply	O(nk)

 

2. Comparison of time efficiency of list.pop() method

What we would expect to see is that the time required to pop from the end of the list will stay constant even as the list grows in size, while the time to pop from the beginning of the list continue to increase as the list grows.

 

import timeit 

popzero = Timer("x.pop(0)", "from __main__ import x")
popend = Timer("x.pop()", "from __main__ import x")
print("pop(0)   pop()")
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)
    print(f"{pz:.5f}, {pt:.5f}")

 

We can see that as the list gets longer and longer the time it takes to pop(0) also increases(𝑂(𝑛)) while the time for pop stays very flat(𝑂(1)).

 

 

 

Source from : https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Lists.html