Complexity analysis guide · 6/6

Real-World Use

Complexity analysis is not just for exams. It is what you reach for when deciding whether a service survives ten times more data, which data structure to use, and where a slowdown comes from. This chapter shows where complexity surfaces in real systems, the usual traps, and where to read further.

Know the cost of your standard library

The same task can have a different complexity depending on the data structure. Common Python costs:

Operation	`list`	`dict` / `set`	`collections.deque`
Append at the end	`O(1)` amortized	`O(1)` average	`O(1)`
Insert/remove at the front	`O(n)`	n/a	`O(1)`
Membership (`in`)	`O(n)`	`O(1)` average	`O(n)`
Index access	`O(1)`	n/a	`O(1)` at the ends, `O(n)` in the middle
Sorting (`sorted`)	`O(n log n)`	n/a	n/a

A queue built on a list with repeated pop(0) shifts every remaining element each time, so draining it is O(n²). deque.popleft() makes it O(n).

from collections import deque

def drain_list(n):
    q = list(range(n))
    while q:
        q.pop(0)          # O(n) each time

def drain_deque(n):
    q = deque(range(n))
    while q:
        q.popleft()       # O(1)

Databases and indexes

Searching on a column without an index makes the database scan the whole table (O(n)). A B-tree index brings lookups down to O(log n), at the cost of extra storage and work on every write. When a query plan (EXPLAIN) shows a full scan, that is the first place to look.

The N+1 query problem in application code is the same issue. Fetching n rows and then sending one more query per row means n round trips, even if each one is fast. A join or a single IN (...) query makes the number of round trips constant.

# N+1: one query per user
for user in users:
    orders = db.query("SELECT * FROM orders WHERE user_id = ?", user.id)

# batched: one query
ids = [user.id for user in users]
placeholders = ", ".join("?" * len(ids))
orders = db.query(f"SELECT * FROM orders WHERE user_id IN ({placeholders})", *ids)

Questions about this chapter?

Real-World Use

Know the cost of your standard library

Databases and indexes

When average and worst case differ: hashing and regex

Common pitfalls

Further reading

Summary

0 comments