With profiling, memory profiling, and benchmarking established as measurement tools, this lesson covers what to actually DO once you've found a real bottleneck — in the order of leverage that experienced engineers reach for them, algorithmic improvements first, micro-optimizations last.
1Highest Leverage First: Algorithmic Complexity
When profiling (from the earlier lesson in this section) points at a specific function as the dominant cost, the single highest-leverage question to ask is: what is this function's actual algorithmic complexity, and is there a lower-complexity approach to the same problem? find_duplicates_slow's single, visible for loop looks linear at a glance, but item in seen — checking membership in a list — is itself an O(n) operation (Python must, in the worst case, check every element), and it runs once per iteration of the outer loop, making the true total cost O(n) × O(n) = O(n²), a hidden quadratic cost invisible from the code's surface shape alone.
Swapping seen from a list to a set changes nothing about the algorithm's *logic* — the code reads almost identically — but changes its complexity fundamentally: item in seen on a set is O(1) on average (a hash table lookup), making the overall function O(n) instead of O(n²). For a list of 1,000 items, that's the difference between roughly 1,000 and roughly 1,000,000 operations — a gap that grows without bound as input size increases, dwarfing what any lower-level optimization could ever achieve on the O(n²) version.
This is precisely why algorithmic fixes are the first thing to look for once profiling identifies a bottleneck: a complexity-class improvement (O(n²) → O(n), or O(n) → O(log n)) scales its benefit with input size, while every other optimization technique in this lesson — idiomatic built-ins, caching, compiled extensions — provides a fixed, bounded speedup multiplier that eventually gets swamped by a bad complexity class at sufficient scale.
# O(n^2): 'in' on a list is O(n), called n times inside the loop
def find_duplicates_slow(items: list) -> list:
seen = []
duplicates = []
for item in items:
if item in seen: # O(n) list search, every iteration
duplicates.append(item)
seen.append(item)
return duplicates
# O(n): 'in' on a set is O(1) average case
def find_duplicates_fast(items: list) -> list:
seen = set()
duplicates = []
for item in items:
if item in seen: # O(1) set lookup
duplicates.append(item)
seen.add(item)
return duplicatesO(n²) → O(n) — the single highest-leverage change available
2Second Leverage: Idiomatic Built-Ins Over Manual Loops
Once the algorithmic complexity is already optimal, the next highest-leverage category of improvement is reaching for built-in functions and idiomatic operations instead of an equivalent hand-written Python loop. sum(numbers) and a manual total = 0; for x in numbers: total += x loop compute the identical result with identical algorithmic complexity (both O(n)) — the difference is entirely about *constant-factor* overhead: sum()'s iteration happens inside CPython's C implementation, executing compiled machine code per element, while a Python-level for loop executes actual Python bytecode instructions (loop control, attribute lookups, the += operation) for every single iteration, each carrying real interpreter overhead a compiled C loop simply doesn't have.
This same principle explains why list comprehensions are typically faster than an equivalent for loop with .append() calls (comprehensions have a more optimized bytecode pattern), why str.join() beats repeated += string concatenation (avoiding the repeated reallocation an immutable string's += implies), and why NumPy's vectorized array operations dramatically outperform an equivalent manual Python loop over array elements (NumPy's operations run entirely in compiled C/Fortran code, processing the whole array per call instead of once per Python-level loop iteration).
The practical habit this builds: before writing a manual loop for a common operation (summing, filtering, transforming, joining), check whether a built-in or standard-library function already expresses that same intent — it's very often both more readable *and* meaningfully faster, since these built-ins are specifically implemented to minimize per-element Python-level overhead.
# Slower: manual Python-level loop
total = 0
for x in numbers:
total += x
# Faster: sum() is implemented in C, avoiding per-iteration Python bytecode overhead
total = sum(numbers)Same O(n) complexity, lower constant factor — C implementation vs Python bytecode
3Last Resort: Caching and Compiled Extensions, After the Above Are Exhausted
Only once the algorithm is already optimal for the problem and idiomatic built-ins are already in use does it make sense to reach for lower-level, more specialized tools. functools.lru_cache (covered in full depth in the functools lesson) trades memory for speed by memoizing a pure function's results — a legitimate, high-value optimization specifically when the same expensive, deterministic computation is repeated with the same arguments across a program's execution, but it doesn't help at all if a function is never actually called twice with the same arguments.
Beyond caching, for the genuinely rare case where a specific, profiled-and-confirmed hot inner loop remains the bottleneck even after algorithmic and idiomatic fixes, compiled-extension approaches become relevant: NumPy's vectorized operations for numerical work (covered extensively in this platform's NumPy course), Cython for compiling performance-critical Python-like code to C, or PyO3/pyo3 for writing a hot path in Rust and exposing it to Python — all trading implementation complexity and a compiled build step for genuine, substantial speedups on code that's already been confirmed, through profiling, to be both correctly algorithmically optimal and genuinely the bottleneck.
The ordering matters as much as the individual techniques: reaching for a compiled extension before confirming the algorithm is optimal is a common and costly mistake — a beautifully optimized O(n²) algorithm rewritten in Rust is still O(n²), and will eventually be outperformed by a plain, un-optimized O(n) Python implementation at sufficient input size. Measure first, fix complexity first, reach for idiomatic built-ins second, and treat caching and compiled extensions as the final, narrowly-scoped tools for a specifically confirmed, unavoidable bottleneck.
from functools import lru_cache
@lru_cache(maxsize=None)
def expensive_pure_computation(n: int) -> int:
... # covered in depth in the functools lesson
# Beyond caching: NumPy's vectorized operations, or a compiled
# extension (Cython, Rust via PyO3) for the rare, truly hot inner loopIn that order, always
4Step-by-Step Breakdown
The biggest performance win is almost never a micro-optimization — it's usually an algorithmic complexity fix that profiling correctly pointed you toward. Let's cover optimization in the right order.
The highest-leverage fix is almost always algorithmic: an O(n^2) membership check hidden inside a loop is often the REAL bottleneck profiling reveals.
Checkpoint: Why is find_duplicates_slow O(n^2) overall, even though it only has one for loop?
- →The 'item in seen' check is itself O(n) on a list, and it runs once per iteration of the outer loop, making the total cost O(n) × O(n) = O(n²)
- →Python's for loops are inherently O(n^2) regardless of what's inside them
The second-highest leverage: idiomatic, built-in operations are usually implemented in C and dramatically faster than an equivalent hand-written Python loop.
Checkpoint: Why is sum(numbers) typically faster than an equivalent manual for-loop accumulator in Python?
- →sum() is implemented in C and avoids the per-iteration overhead of executing Python bytecode for each loop step
- →sum() automatically runs across multiple CPU cores in parallel
Only AFTER algorithmic and idiomatic fixes are exhausted does it make sense to reach for lower-level tools -- caching, or offloading to a compiled extension.
That completes Python Performance — profiling, memory profiling, benchmarking, and optimization technique give you the full measure-then-improve discipline. Next, Advanced Error Handling deepens the resilience patterns this curriculum builds on.
Find Real Duplicates in O(n). Finish find_duplicates_fast(): a set lookup is O(1) versus O(n) for a list.
Level Up 🚀
Advanced cheat sheets, SEO tricks, and interview prep for this topic.
Browser Support
Fully supported (via server-side Python execution).
Fully supported (via server-side Python execution).
Fully supported (via server-side Python execution).
Fully supported (via server-side Python execution).
Best Practices
Always check algorithmic complexity before reaching for any lower-level optimization
A complexity-class fix (O(n²) → O(n)) scales its benefit with input size and typically dwarfs anything achievable through micro-optimization, caching, or compiled extensions on a suboptimal algorithm.
Prefer idiomatic built-ins and standard-library functions over hand-written loops for common operations
They typically run substantially compiled C code per element instead of interpreted Python bytecode, offering real constant-factor speedups at no cost to readability — often improving both simultaneously.
Frequent Bugs
Reaching for caching, compiled extensions, or micro-optimizations before checking whether the underlying algorithm's complexity class is actually optimal for the problem, missing the highest-leverage fix available.
Always analyze the algorithmic complexity of a profiled bottleneck first — a complexity-class improvement almost always dwarfs any benefit from lower-level optimization applied to a suboptimal algorithm.
Real-World Examples
Fixing a Quadratic Deduplication Bottleneck at Scale
A data pipeline's deduplication step, using list-based membership checking, works fine in testing with small samples but times out in production on datasets with hundreds of thousands of records.
# Before: O(n^2), fine for 100 records, catastrophic for 500,000
def deduplicate_slow(records: list) -> list:
seen = []
result = []
for record in records:
if record.id not in seen:
seen.append(record.id)
result.append(record)
return result
# After: O(n), scales linearly regardless of dataset size
def deduplicate_fast(records: list) -> list:
seen = set()
result = []
for record in records:
if record.id not in seen:
seen.add(record.id)
result.append(record)
return result