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)

When average and worst case differ: hashing and regex

A hash table's O(1) is an average. If many keys land in the same bucket, operations degrade to O(n). Hash flooding attacks have exploited this by sending deliberately colliding keys, which is why Python mixes a per-process random seed into string hashes and Java's HashMap turns crowded buckets into balanced trees.

Regular expressions have the same trap. In a backtracking engine, a pattern like (a+)+$ can try exponentially many ways to fail on a non-matching input and stall a server (ReDoS). For patterns that see user input, avoid nested quantifiers and cap the input length.

import re
import time

pattern = re.compile(r"(a+)+$")
for n in (18, 20, 22):
    text = "a" * n + "!"
    start = time.perf_counter()
    pattern.match(text)
    print(n, f"{time.perf_counter() - start:.3f}s")   # about 4x for every 2 extra characters

Common pitfalls

Ignoring constants on small inputs: for a few dozen elements, O(n²) insertion sort can beat an O(n log n) sort. That is why real sort routines (Timsort, introsort) switch to insertion sort for short runs.
Ignoring the memory hierarchy: two O(n) loops can differ several times in speed because a sequential array scan is cache-friendly and pointer chasing through a linked list is not.
Building strings by repeated concatenation: depending on the language and implementation this can be O(n²); collect pieces and use "".join(parts).
Guessing instead of measuring: bottlenecks are often somewhere unexpected. Profile first, for example with cProfile.

Summary

Knowing standard library costs helps you avoid hidden O(n) operations such as pop(0) and in list.
Many real performance fixes, like indexes and batched queries, drop the complexity by one class.
Where average and worst case differ, attacks or unusual inputs can trigger the worst case.
Complexity is the starting point; measure to see constants and memory effects.

Questions about this chapter?