Python hides loops inside short lines. One innocent line inside a loop can turn a fast program into a slow one. This lesson lists the costs you need to know.
The cost of common operations
Here n is the size of the list, string, set or dict, and k is the size of a slice or of the other operand.
| Operation | Cost | Why |
|---|---|---|
a[i], a[i] = x, len(a) | O(1) | the place is worked out directly |
a.append(x), a.pop() | O(1) amortised | lesson 7 |
a.pop(0), a.insert(0, x) | O(n) | every later value moves |
x in a, a.index(x), a.count(x), a.remove(x) | O(n) | checks values one by one |
a[i:j] | O(k) | copies k = j − i values |
a + b, sum(a), min(a), max(a) | O(n) | reads every value |
sorted(a), a.sort() | O(n log n) | SORT station |
x in s, s.add(x), d[k] | O(1) average | hashing (HASH station) |
d.popleft(), d.appendleft(x) on a deque | O(1) | a deque can grow at both ends |
s + t on strings | O(n + k) | strings cannot change, so a new one is built |
Removing from the front
Values in a list sit side by side from index 0. Remove the first one and every other value must move one place to the left. Step through it:
Take values off the front, one at a time, with a.pop(0). A Python list keeps its values side by side from index 0.
A queue that serves people in the order they arrived takes from the front. Written with pop(0), it is Θ(n²) overall. Written with collections.deque, it is Θ(n). The STAQ station uses deques throughout.
Building strings
A Python string cannot be changed after it is made. So s = s + t builds a whole new string and copies both parts into it. In a loop, the copies grow each time:
out = ""
for w in words:
out = out + w + " " # may copy everything so far, every time
out = " ".join(words) # one pass: O(total length)
CPython sometimes avoids the copy in the first version, but you cannot rely on it. Collect the parts in a list and join them once.
Slices and copies
a[1:] looks like one step, but it copies n − 1 values. A recursive function that passes a[1:] to itself does n + (n − 1) + … + 1 copying in total, which grows with n times n: Θ(n²). Pass an index instead:
def total(a): # Θ(n²) because of the slices
return 0 if not a else a[0] + total(a[1:])
def total(a, i=0): # Θ(n)
return 0 if i == len(a) else a[i] + total(a, i + 1)
in on a list
x in a on a list checks values one by one. Inside a loop over n values, it makes the whole loop Θ(n²). If you test membership more than a few times, build a set once and test against the set.
Now try BIGO-P3, Keep the first of each, where in on a list is the slow part.
BIGO-8 counts as completed once you step through the figure to the last step.