Python: коллекции, часть 2/4: индексирование, срезы, сортировка

Было бы восхитительно, если была бы также приведена сложность алгоритма, где это уместно.
Как например,

l = [1, 2, 3, 4]  # List
l.pop(0)          # -> 1 | O(n)
l.pop()           # -> 4 | O(1)

d = deque(l)  # Double-linked list
d.popleft()   # -> 1 | O(1)
d.pop()       # -> 4 | O(1)

Получился бы отличный справочник.