Algorithmic complexity in practice

What you'll learn

• Read Big-O notation as "how does the time grow when the input grows"
• Measure the growth of real code instead of guessing, and match it to O(1), O(n), O(n log n), O(n²)
• Know the complexity of the operations you use daily on lists, dicts, and sets
• Pick the shape of a solution before writing it, and recognize the nested loop that will not scale

Concept

Big-O notation describes how the cost of an operation grows as its input grows, ignoring constants and small inputs. O(1) means the cost does not depend on the size: a dictionary lookup. O(n) means it grows in proportion: a loop over a list. O(n²) means doubling the input quadruples the cost: a loop inside a loop over the same data. O(log n) barely grows: binary search halves the problem each step. O(n log n) is the cost of good sorting. The letters are less important than the question they answer: what happens to this code when the data is a thousand times bigger than my test?

You do not need to derive these from theory; you can measure them. Time an operation at several input sizes, say 1,000, 10,000, and 100,000, and look at the ratios. If ten times the data costs ten times the time, it is linear. If it costs a hundred times, it is quadratic, and it will be a thousand times slower again at a million. This is the single most useful performance habit: measure growth, not a single timing. A function that takes two milliseconds on your test data is fine or a disaster depending on its shape, and only the growth tells you which. A handful of costs are worth knowing by heart, though, because they decide the shape before you ever measure it: what a dictionary or set lookup costs, what scanning a list costs, what inserting at the front costs, what sorting costs, and what a loop inside a loop costs.

That table is the daily payoff: the same question answered by a list or a set differs by an order of growth. The nested loop is the shape to recognize. "For every order, find the matching customer in the customer list" is O(n × m) with a list scan inside; build a dictionary of customers keyed by id first, and it becomes O(n + m). Sorting once and using bisect, or grouping once into a dictionary, replaces most quadratic loops. The pattern is always the same: do the expensive preparation once, then make each of the n steps cheap.

Complexity is not everything. Constants matter for small inputs, memory matters, and a clear O(n²) on a hundred items beats a clever O(n log n) with a bug. The discipline is to know the shape of what you wrote, to measure growth when the data could be large, and to fix the order of growth before tuning constants, which is the next lesson's subject. Most performance problems in real code are a hidden O(n²), and they are found by asking "what is inside this loop" rather than by profiling.

Code

Measuring growth. Each function is timed at three sizes; the ratios between consecutive timings reveal the shape without any theory.

# measure_growth.py
import time


def linear(n):
    return sum(range(n))


def quadratic(n):
    items = list(range(n))
    return sum(1 for a in items for b in items if a + b == n)


def constant(n):
    d = {i: i for i in range(n)}
    return d[n - 1]


def growth(fn, sizes):
    times = []
    for n in sizes:
        start = time.perf_counter()
        fn(n)
        times.append(time.perf_counter() - start)
    return [round(times[i + 1] / max(times[i], 1e-9), 1) for i in range(len(times) - 1)]


lin = growth(linear, [100_000, 1_000_000])
quad = growth(quadratic, [500, 2_000])
print("10x input, linear time ratio roughly 10x:", 5 <= lin[0] <= 20)
print("4x input, quadratic time ratio roughly 16x:", 8 <= quad[0] <= 40)

10x input, linear time ratio roughly 10x: True
4x input, quadratic time ratio roughly 16x: True

List versus set versus dict for the everyday operations, at a size where the difference is unmistakable.

# operations.py
import time
from collections import deque

n = 200_000
items = list(range(n))
as_set = set(items)
as_dict = {i: i for i in items}


def timed(label, fn):
    start = time.perf_counter()
    fn()
    return time.perf_counter() - start


list_in = timed("list in", lambda: [x in items for x in range(0, n, n // 200)])
set_in = timed("set in", lambda: [x in as_set for x in range(0, n, n // 200)])
print("membership: set at least 100x faster than list:", list_in / max(set_in, 1e-9) > 100)

pop0 = timed("pop(0)", lambda: [items.copy().pop(0) for _ in range(20)])
q = deque(items)
popleft = timed("popleft", lambda: [q.popleft() for _ in range(20)])
print("front removal: deque much faster than list:", pop0 / max(popleft, 1e-9) > 20)

print("dict lookup is constant:", as_dict[n - 1] == n - 1)

membership: set at least 100x faster than list: True
front removal: deque much faster than list: True
dict lookup is constant: True

The quadratic loop and its linear rewrite: matching orders to customers by scanning versus by dictionary. Same answer, different order of growth.

# join.py
import time

customers = [{"id": i, "name": f"c{i}"} for i in range(20_000)]
orders = [{"id": i, "customer_id": (i * 7) % 20_000} for i in range(20_000)]


def join_scan(orders, customers):
    out = []
    for order in orders:
        for customer in customers:
            if customer["id"] == order["customer_id"]:
                out.append((order["id"], customer["name"]))
                break
    return out


def join_index(orders, customers):
    by_id = {c["id"]: c for c in customers}
    return [(o["id"], by_id[o["customer_id"]]["name"]) for o in orders]


start = time.perf_counter()
fast = join_index(orders, customers)
fast_t = time.perf_counter() - start

start = time.perf_counter()
slow = join_scan(orders[:2_000], customers)
slow_t = time.perf_counter() - start

print(fast[:2], len(fast))
print("index join on 20k rows faster than scan join on 2k rows:", fast_t < slow_t)

[(0, 'c0'), (1, 'c7')] 20000
index join on 20k rows faster than scan join on 2k rows: True

Sorting once and searching with bisect, against repeated linear searches. Logarithmic search wins as soon as there are many lookups.

# bisect_demo.py
import bisect
import time

values = sorted(range(0, 2_000_000, 3))
targets = list(range(0, 2_000_000, 997))


def linear_search(x):
    return x in values


def binary_search(x):
    i = bisect.bisect_left(values, x)
    return i < len(values) and values[i] == x


start = time.perf_counter()
lin = [linear_search(t) for t in targets[:200]]
lin_t = time.perf_counter() - start

start = time.perf_counter()
bis = [binary_search(t) for t in targets]
bis_t = time.perf_counter() - start

print(lin == bis[:200], sum(bis), "hits of", len(targets))
print("bisect over all targets faster than linear over a tenth of them:", bis_t < lin_t)

True 669 hits of 2007
bisect over all targets faster than linear over a tenth of them: True

Try it yourself

Create dedupe.py with three functions that remove duplicates from a list while keeping the first occurrence: one using if x not in result on a list, one using a seen-set, and one using dict.fromkeys. Time each at 1,000, 10,000, and 100,000 items and print the growth ratios. Then find any nested loop in your earlier project code, work out its complexity in a comment, and rewrite it with a dictionary if it is quadratic.

Common mistakes

• Timing once at one size. A single number hides the shape; time at several sizes and read the ratios.
• in on a list inside a loop. It is the most common accidental O(n²); build a set or dict before the loop.
• Optimizing constants before the order. Shaving a loop body from 3µs to 2µs does nothing for an O(n²) that should be O(n).

What's next

• Big-O answers "how does cost grow with input"; measure growth at several sizes and read the ratios.
• Dict and set operations are O(1), list scans are O(n), sorting is O(n log n), nested loops over the same data are O(n²).
• Prepare once (a dict, a sorted list), then make each step cheap; fix the order of growth before tuning.

You can predict how code scales. Next you will find out where a slow program actually spends its time, with profilers, and apply the handful of speedups that matter.