Without knowing Python's built-in types you cannot estimate real complexity: the single line x in a costs O(n) for a list and O(1) for a set. The tables below follow the documented behaviour of CPython (the TimeComplexity page on python.org), and we will check each claim with a small measurement.
list
| Operation | Cost |
|---|---|
a[i], a[i] = x, len(a) | O(1) |
a.append(x), a.pop() | O(1) (append amortized) |
a.insert(i, x), a.pop(i), a.pop(0), del a[i] | O(n): items shift |
x in a, a.index(x), a.count(x), a.remove(x) | O(n) |
a[i:j], a.copy() | O(j - i), O(n): a copy |
a.extend(b), a + b | O(len(b)), O(len(a) + len(b)) |
min(a), max(a), sum(a), a.reverse() | O(n) |
a.sort(), sorted(a) | O(n log n), O(n) on sorted input |
from timeit import timeit
n = 100_000
data = list(range(n))
at_end = timeit(lambda: (data.append(0), data.pop()), number=2000)
at_front = timeit(lambda: (data.insert(0, 0), data.pop(0)), number=2000)
print("front is much slower than end:", at_front > 5 * at_end)front is much slower than end: True