Algorithms That Finish In Time: A Complexity Gut Check

You write a function, run it on your test data, and it works fine. Then it hits production data — 500,000 rows instead of 500 — and the request times out. This happens constantly, and it's almost always a complexity problem hiding behind code that looked reasonable at small scale.

Why your laptop lied to you

An O(n²) algorithm running on 100 items does 10,000 operations. That's instant on any machine. Run the same algorithm on 100,000 items and you're at 10 billion operations — minutes or hours instead of milliseconds. The jump from n to n² doesn't feel dangerous until n gets large, which is exactly why it slips through code review and local testing.

A classic example: checking for duplicates with a nested loop.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

This is O(n²). Swap it for a set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Now it's O(n). Set lookups are average O(1), so the whole function scales linearly instead of quadratically. On 10,000 items that's the difference between roughly 100 million comparisons and 10,000.

Measure before you optimize

Don't guess. Use timeit for microbenchmarks:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

For bigger functions, profile with cProfile:

python -m cProfile -s cumulative myscript.py

Look at the cumtime column. If one function eats 90% of runtime, that's your target. Optimizing code that isn't the bottleneck wastes your time and adds complexity for no gain.

Common patterns that quietly become slow

Repeated list membership checks. if x in my_list is O(n) for a list but O(1) average for a set or dict. If you're checking membership inside a loop, that O(n) check inside an O(n) loop gives you O(n²) overall. Swap the list for a set and you're back to O(n).

String concatenation in a loop. In Python, result += chunk inside a loop over strings is O(n²) in the worst case because strings are immutable and each concatenation copies the whole thing. Use ''.join(chunks) instead — it builds the string once.

Sorting when you don't need to. sorted() is O(n log n). If you're calling it inside a loop to just find the max or min each iteration, use max()/min() (O(n)) or better, a heap (heapq) if you need the running extreme repeatedly. heapq.nlargest(k, data) is O(n log k), much cheaper than sorting the whole list when k is small.

Recursive functions without memoization. Naive recursive Fibonacci is O(2ⁿ) because it recomputes the same subproblems over and over. Add functools.lru_cache and it drops to O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Reading Big O off real code, fast

Count nested loops over the same input — that's usually your exponent. A single loop is O(n). A loop inside a loop is O(n²) unless the inner loop's range shrinks (like in bubble sort's optimized form, still O(n²) worst case but fewer comparisons). Recursive calls that split the problem in half, like binary search or merge sort, point to O(log n) or O(n log n). Recursive calls that branch into multiple calls per level, like naive Fibonacci, point to exponential time — a strong signal you need memoization or an iterative rewrite.

A good habit: before you write nested loops or recursion over user-facing data, ask what n could realistically be in production, not in your test file. If n could hit six figures, an O(n²) solution needs a second look before it ships.

For more on complexity analysis, sorting algorithms, and profiling tools, check out the Python and Computer Science segments on Korra Studio.