The Real Cost of Python Operations
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Big-O counts the loops you write. Python also hides loops inside in, count, slices and string joins. Knowing what each operation really costs is what turns an O(n²) solution into an O(n) one.
Lists: quick at the end, slow at the front
Amortised cost is the average cost per operation over many operations. list.append is O(1) amortised: almost always instant, with a rare resize that copies the whole list.
A list keeps its items side by side in memory. Reading items[i] or adding at the end is quick. Adding or removing at the front moves every other item one place.
items = list(range(1000))moved = 0for value in range(5): moved += len(items) items.insert(0, value)print(moved)Example 1 · Front of a queue: list vs deque
from collections import deque
tickets = list(range(2000))shifted = 0while tickets: shifted += len(tickets) - 1 tickets.pop(0)print(shifted)
line = deque(range(2000))handled = 0while line: line.popleft() handled += 1print(handled)1999000 2000
What this code does
pop(0)moves every remaining ticket one place left: nearly two million moves in total, O(n²).deque.popleft()removes the front in O(1), so 2000 tickets cost 2000 steps.- Use a deque whenever you take from the front.
Five inserts at the front shifted about five thousand items. The same five appends would shift none.
dict and set jump straight to the key
Hash table is the structure behind dict and set. It turns each key into a number and stores it at that place, so lookup, insert and delete take O(1) on average.
A dict or set turns each key into a number, its hash, and goes straight to that place. Average cost is O(1), however large it is. A list has to look at items one by one.
Example 2 · A thousand lookups: list vs set
ids = list(range(1000))queries = list(range(999, 1999))
list_checks = 0found = 0for q in queries: for item in ids: list_checks += 1 if item == q: found += 1 breakprint(found, list_checks)
id_set = set(ids)set_checks = 0found_set = 0for q in queries: set_checks += 1 if q in id_set: found_set += 1print(found_set, set_checks)1 1000000 1 1000
What this code does
- The scan visits the whole list for every query that is missing: one million checks.
- The set answers each query in one lookup: one thousand checks.
- Same answer, one thousand times less work.
Example 3 · Counting words: count() in a loop vs Counter
from collections import Counter
words = ["a", "b", "a", "c", "b", "a"] * 100steps = 0counts = {}for word in words: steps += len(words) counts[word] = words.count(word)
fast = Counter(words)print(counts == dict(fast), steps, len(words))True 360000 600
What this code does
words.count(word)scans all 600 words, and it runs 600 times: 360000 steps, O(n²).Countermakes one pass over the words: 600 steps, O(n).- Both give the same counts.
Example 4 · dict and set jump straight to the key
class Probe: comparisons = 0
def __init__(self, value): self.value = value
def __hash__(self): return hash(self.value)
def __eq__(self, other): Probe.comparisons += 1 return self.value == other.value
as_list = [Probe(i) for i in range(1000)]as_set = set(as_list)Probe.comparisons = 0print(Probe(999) in as_list, Probe.comparisons)Probe.comparisons = 0print(Probe(999) in as_set, Probe.comparisons)True 1000 True 1
What this code does
- The list compared 1000 times.
- The set compared once, after the hash led it to the right place.
Strings cannot change, so building one copies
A str is immutable. Each result += piece builds a new string and copies the old text into it. "".join(pieces) joins everything in one pass and copies each piece once.
pieces = ["ab"] * 1000copied = 0result = ""for piece in pieces: copied += len(result) + len(piece) result += pieceprint(copied)print(len("".join(pieces)))Example 5 · Doubling n quadruples += copying
def copies_with_plus(n): copied, size = 0, 0 for _ in range(n): copied += size + 1 size += 1 return copied
for n in (100, 200, 400): print(n, copies_with_plus(n))100 5050 200 20100 400 80200
What this code does
- Each
+=copies the whole string so far plus the new character. - Doubling n from 100 to 200 to 400 multiplies the copying by about four each time: O(n²).
- With join the copying would stay at n.
The loop copied about a million characters to build a 2000-character string. CPython sometimes speeds += up, but do not rely on it. join always costs O(n).
Slices and other hidden copies
A slice items[a:b] builds a new list of b - a items. sorted copies and sorts. in, count and index scan. Count the hidden work before you write it inside a loop.
items = list(range(8))copied = 0while items: items = items[1:] copied += len(items)print(copied)Example 6 · Slicing inside recursion
copied = 0
def total_slice(items): global copied if not items: return 0 copied += len(items) - 1 return items[0] + total_slice(items[1:])
print(total_slice(list(range(1, 301))), copied)print(sum(range(1, 301)))45150 44850 45150
What this code does
- Every call slices off the first item, which copies all the others.
- 300 items caused 44850 copied items: O(n²) time hidden in a short function.
- A loop, or an index passed down, avoids every copy.
Example 7 · Sort once or scan again and again
prices = [37, 12, 90, 5, 61, 48, 23, 77]
ordered = sorted(prices)print(ordered[:3])
rest = prices[:]smallest = []scans = 0for _ in range(3): scans += len(rest) value = min(rest) rest.remove(value) smallest.append(value)print(smallest, scans)[5, 12, 23] [5, 12, 23] 21
What this code does
- One sort costs O(n log n) and answers any "k smallest" question.
- Repeating min costs about k * n, so it wins only when k is very small.
- Choose by the size of k and n, not by habit.
Dropping the first item eight times copied 28 items. For n items it copies about n²/2, so use an index or a deque instead.
Next step
Check your understanding
12 quick questions