When O(n²) Kills Your DataFrame

You have a working pipeline. It passes tests, produces correct output, and runs fine on 10,000 rows. You push it to production with 2,000,000 rows and it takes forty minutes instead of one.

Nothing is broken. The complexity is.

This lesson is about the gap between correct and scalable — specifically the O(n²) traps that appear constantly in data work, and the O(n+m) patterns that replace them.

The trap: correctness without scalability

Here is a join that looks reasonable:

# For every order, find the matching customer name
enriched = []
for order in orders:          # n iterations
    for customer in customers:    # m iterations each
        if order["customer_id"] == customer["id"]:
            enriched.append({**order, "name": customer["name"]})
            break

This is O(n × m). If orders has 100,000 rows and customers has 50,000 rows, that is 5,000,000,000 comparisons in the worst case. At 10 million comparisons per second, you are waiting eight minutes for a join.

The same pattern appears in other shapes:

# Repeated boolean-mask filter inside a loop — O(n × m)
for tag in my_tags:
    subset = df[df["tag"] == tag]   # scans all n rows each time
    process(subset)

# df.apply doing a per-row list scan — O(n × m)
lookup_list = [{"key": k, "val": v} for k, v in pairs]
df["result"] = df["id"].apply(
    lambda x: next((d["val"] for d in lookup_list if d["key"] == x), None)
)

# Growing a frame with repeated concat in a loop — O(n²) due to copies
# (each concat writes 1+2+3+...+k chunks — a triangular sum proportional to k²)
result = pd.DataFrame()
for chunk in chunks:
    result = pd.concat([result, chunk])   # copies the whole frame each time

All four patterns share the same shape: an outer scan triggers an inner scan (or an inner copy) of proportional size.

The fix: hash-based joins and precomputed lookups

The insight from hash tables carries directly here. Instead of scanning, index once and query in O(1).

Pattern 1: replace a nested-loop join with a dict index

# Build index once: O(m)
customer_index = {c["id"]: c["name"] for c in customers}

# One pass over orders: O(n)
enriched = [
    {**order, "name": customer_index.get(order["customer_id"], "unknown")}
    for order in orders
]
# Total: O(n + m) instead of O(n × m)

In pandas, df.merge does this for you — it builds a hash index internally.

enriched = orders.merge(customers[["id", "name"]], left_on="customer_id", right_on="id", how="left")

Pattern 2: precompute a set for membership tests

# Bad: O(n × m)
result = [x for x in big_list if x in other_big_list]

# Good: build set once O(m), then O(1) per lookup
lookup_set = set(other_big_list)
result = [x for x in big_list if x in lookup_set]

Pattern 3: map with a dict, don’t loop with a filter

In pandas, .map(dict) is a single vectorized pass. It is the direct replacement for .apply(lambda row: ...) with a list scan inside.

# Bad: O(n × m)
df["label"] = df["code"].apply(lambda c: next((v for k, v in code_pairs if k == c), None))

# Good: O(n + m)
code_map = dict(code_pairs)
df["label"] = df["code"].map(code_map)

Pattern 4: collect, then concat once

# Bad: O(n²) — each concat copies the growing frame
result = pd.DataFrame()
for chunk in chunks:
    result = pd.concat([result, chunk])

# Good: O(n) — one concat at the end
parts = []
for chunk in chunks:
    parts.append(chunk)
result = pd.concat(parts, ignore_index=True)

See it live: nested loop vs hash join

Run this code. It joins two lists of records by key — first with a nested loop (O(n·m)), then with a dict index (O(n+m)) — and counts comparisons for both.

As n doubles, nested comparisons roughly quadruple (n²). Hash comparisons grow by 2n — linear. At n = 2000 the gap is already ~500×. On a real dataframe at one million rows it is measured in hours vs seconds.

In pandas: df.merge is the hash join. .map(dict) is the dict lookup. Both are O(n+m). iterrows with a condition check inside is the nested loop.

Quick check