Performance
15 min
You've already met the tools for this course — hash tables, sets, sorting, comprehensions. This module is about a habit: noticing when everyday code is accidentally doing more work than it needs to, usually by hiding an O(n) operation inside a loop that runs n times, silently turning O(n) work into O(n²).
The classic trap: checking membership in a list inside a loop.
# O(n * m) — "x in slow_list" is O(n) each time, called m times
def find_common_slow(a, slow_list):
return [x for x in a if x in slow_list]
# O(n + m) — build a set once, "x in fast_set" is O(1) each time
def find_common_fast(a, b):
fast_set = set(b)
return [x for x in a if x in fast_set]
Both return the same answer — but has_duplicates_slow does up to n²/2 comparisons, while has_duplicates_fast does at most n, trading a little memory (the set) for a lot of speed.
Another common trap: building a large string with repeated += in a
loop. Because Python strings are immutable, every += allocates a brand
new string and copies the old contents into it — do that n times and
you've copied O(n²) characters total.
# O(n²) — each += copies everything accumulated so far
result = ""
for word in words:
result += word + " "
# O(n) — join does exactly one pass, allocating once
result = " ".join(words)
str.join is the standard fix — reach for it any time you're building a
string from many pieces in a loop.
Write `has_duplicates_fast(nums)`, returning True if `nums` contains any duplicate value. Use a set for O(n) — don't compare every pair (that's O(n²)).
Write `build_greeting_fast(names)` that joins every name in `names` with ', ' into a single string. Use `str.join`, not `+=` in a loop.
Why is repeatedly doing `result += item` to build a large string in a loop O(n²), while `''.join(items)` is O(n)?
You can spot an accidental O(n²) hiding in "membership check inside a loop" or "string += inside a loop," and fix both with a set and str.join.