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
