Big-O complexity, and how to approach it in real code

Big-O notation describes how the work a piece of code does grows as its input grows. It doesn’t say how fast code is. It says what happens when the data gets ten times bigger, and in production, that’s often the question that matters.

Timings below were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere. The growth patterns are what count.

What O(n) means

Take a function that looks for a value in a list:

def contains(items, target):
    for item in items:
        if item == target:
            return True
    return False

In the worst case, the value isn’t there, and the loop visits every item. If the list has $n$ items, that’s $n$ comparisons. Double the list, and the work doubles. That’s O(n), or linear time.

The formal definition: $f(n)$ is $O(g(n))$ if there are constants $c$ and $n_0$ so that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$. In plain terms, past some size, $g$ times a constant is an upper bound on growth.

This has two consequences.

Constants are dropped. $3n + 100$ is $O(n)$, because for large $n$, the shape is what matters.

Only the biggest term stays. $n^2 + 1000n$ is $O(n^2)$. At a million items, the $n^2$ term dominates completely.

Three related symbols are less often used: O is an upper bound, Ω is a lower bound, and Θ is a tight bound. Everyday use says “O” while usually meaning Θ.

Measuring a real difference

Looking for a missing value in a list scans everything, a set hashes straight to the answer, and binary search on a sorted list halves the range each step:

The list column grows tenfold with each row, which is O(n). The set column stays flat, which is O(1). Binary search grows slowly, which is O(log n). At a million items, the set is more than 300,000 times faster than the list.

The common classes

At a billion simple operations a second, a trillion steps takes about 17 minutes, while 20 million takes 20 ms.

O(1): constant

The work doesn’t depend on size. Array indexing computes an address directly. A hash table computes where the value should be. “Constant” doesn’t mean fast, only that it doesn’t grow.

O(log n): logarithmic

Each step discards a fixed fraction of the remaining data. Binary search halves the range, so a million items take about 20 steps and a billion take about 30. Multiplying the data by 1,000 adds only 10 steps. That’s why database indexes work so well (Postgres indexes).

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

O(n log n): sorting

Comparison sorts can’t do better than this in general. Sorting is usually so fast that it’s a good building block. Measured with Python’s sorted:

Ten times the data took about 13 times as long, a little over linear.

O(n²): quadratic

Quadratic code is the most common performance bug, because it works fine in testing and then fails on real data. Removing duplicates with a list:

def dedupe_slow(items):
    seen = []
    for item in items:
        if item not in seen:     # O(n) inside an O(n) loop
            seen.append(item)
    return seen

def dedupe_fast(items):
    return list(set(items))

Each row has four times the data. The list version took about 16 times longer, and the set version about 4 times longer. Quadratic code quadruples when data doubles. At 16,000 items it’s nearly 2,000 times slower, and that gap keeps growing.

O(2ⁿ): exponential

Each extra input item doubles the work. The naive Fibonacci function calls itself twice:

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Each increase of 2 multiplies the time by about 2.6, and this is the golden ratio squared, because the true growth is about $1.618^n$. By fib(60), it would take many hours. Adding memoization stores each result, which makes it O(n):

from functools import lru_cache

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

fib(300) took 41.5 µs this way.

How to analyze code

A systematic method works for most code.

1. Define n. What’s growing? There may be several sizes, and they shouldn’t be merged. A function over users and orders is $O(u + o)$ or $O(u \times o)$, not $O(n)$.

2. Sequential code adds.

for x in a:      # O(n)
    work(x)
for y in a:      # O(n)
    work(y)

O(n) + O(n) = O(n).

3. Nested code multiplies.

for x in a:      # n times
    for y in a:  # n times
        work(x, y)

O(n) × O(n) = O(n²).

4. Look inside calls. This is where most bugs hide. A call that looks like one step may be a loop:

for user in users:
    if user.id in banned_list:   # O(b), a hidden loop
        ...

This is O(n × b), not O(n). If banned_list becomes a set, it’s O(n).

5. Check how the loop variable changes. A loop that adds 1 is linear. One that halves or doubles its variable is logarithmic.

6. Count recursion. For a recursive function, multiply calls by work per call. A binary recursion with depth $n$ makes up to $2^n$ calls. A function that splits data in half and does linear work, like merge sort, has $\log n$ levels, each costing $n$, for O(n log n).

The master theorem

Divide-and-conquer recurrences have the form $T(n) = aT(n/b) + f(n)$: $a$ subproblems of size $n/b$, plus combining work.

Space complexity

Memory follows the same analysis. Building a set of seen items uses O(n) memory, and it’s the classic trade: the fast dedupe spends memory to save time.

Recursion uses stack memory too. Each call takes a frame, so depth $n$ means O(n) space, even if no data structure is visible. Python limits recursion depth for this reason.

Best, average and worst case

Big-O is a statement about growth, and it can apply to any case.

Worst cases can be a security issue. A hash table with many colliding keys degrades to O(n), and an attacker who can pick keys can use that to cause a denial of service. Languages randomize string hashing to defend against this. A similar attack, called ReDoS, uses regular expressions with exponential backtracking.

Amortized analysis

Some operations are usually cheap, and occasionally expensive. Appending to a dynamic array normally takes one step, but when the array is full, it allocates a bigger one and copies everything.

If capacity doubles each time, copying a total of $n$ items happens across $n$ appends. Spread over all of them, that’s O(1) each. This is amortized O(1). Most appends are instant, and rare ones are slow, which can show up as a latency spike.

Hidden costs in everyday operations

Knowing what the standard library really does is the most useful practical skill here.

Using a list as a queue

pop(0) shifts every remaining item. Removing a tenth of the items from each list:

Building strings

Strings and bytes are immutable, so s = s + x copies everything so far, which makes a loop O(n²).

How to improve code

Most improvements use one of a few moves.

Hash lookup: two-sum

The nested version checks every pair:

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

def has_pair_fast(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

Sliding window

A moving sum over $k$ items doesn’t need to re-add each window. Adding the new item and subtracting the old one makes each step O(1):

def max_window(nums, k):
    total = sum(nums[:k])
    best = total
    for i in range(k, len(nums)):
        total += nums[i] - nums[i - k]
        best = max(best, total)
    return best

Heaps for top-k

Finding the 10 largest of a million values doesn’t need a full sort:

Complexity in real systems

Big-O shows up well beyond algorithms.

Database queries. A query with no index is a linear scan. Adding an index turns it into O(log n). A query that works on a small test table can bring down production for this reason.

The N+1 problem. A loop that runs one query per item has a network round trip inside an O(n) loop. The constant is about a million times larger than a memory access, so even small values of $n$ hurt.

Nested loop joins. A join on an unindexed column can be O(n × m).

Pagination. OFFSET 1000000 makes a database walk past a million rows, so it’s O(offset). Cursor pagination is O(log n).

Serialization. Reading and writing a whole JSON blob to change one field costs O(size) per update.

Distributed fan-out. One post sent to every follower is O(followers), which is why a news feed needs special handling for accounts with huge audiences.

Regular expressions. Some patterns backtrack exponentially on bad input.

When constants matter

Big-O hides constants, and at small sizes, or on real hardware, they can decide the outcome.

Small inputs. For a handful of items, a linear scan of an array is often faster than a hash table, because it doesn’t compute a hash. Library sorts use insertion sort, an O(n²) algorithm, for tiny ranges for this reason.

Memory locality. Both loops below are O(n), and both read the same 5 million values:

The shuffled version took about nine times longer, purely because of CPU caches. Big-O assumes every memory access costs the same, and on real hardware, that’s far from true. This is why arrays often beat linked lists, even for operations where linked lists have a better Big-O.

Layers. A network call is about a million times slower than a memory access. An O(n) loop of network calls can lose to an O(n²) loop in memory for any realistic $n$.

How to approach it in practice

1. Know your n. A list that can only ever hold 10 items doesn’t need optimizing. One with user-controlled size does.

2. Measure first. Profilers such as cProfile or perf show where time actually goes, and it’s rarely where people guess.

3. Fix the worst growth first. Replacing an O(n²) step is usually worth more than any amount of tuning.

4. Choose the right data structure. Most improvements come from this, not from clever algorithms.

5. Test with realistic sizes. Quadratic code looks fine at 100 rows. Testing at 10 times the expected size reveals it.

6. Prefer clarity until it matters. Simple O(n²) code on a small, bounded input is fine. As Donald Knuth wrote, premature optimization is the root of all evil, in the small part of the code where it doesn’t matter. The rest of that quote is often forgotten: it’s the critical 3% that deserves real attention.

A short code review checklist:

• Is there a loop inside a loop, or a call that hides one?
• Is in used on a list that could be large?
• Is there a query or network call inside a loop?
• Does any input size come from a user?
• Is a collection growing forever?

Reference: data structures

The takeaway

Big-O tells you how code will behave when the data grows. Look for loops, including the ones hidden in library calls, and multiply when they nest. Use hash tables, sorting and the right data structure for most of the gains. Then measure, because constants and caches also matter, and because most code doesn’t need optimizing at all.