Big O Notation Explained With Code Examples

A Python dictionary lookup takes about 100 nanoseconds whether the dict holds 1,000 keys or 1,000,000. A nested loop that checks a list for duplicates takes half a millisecond on 200 items and 136 milliseconds on 3,200. Sixteen times the input, nearly 280 times the wait. Same machine, same Python. Big O notation is the name for that difference.

What Big O notation measures

Big O describes how the running time (or memory use) of a piece of code grows as the input gets larger. It is not a stopwatch reading, and it does not care whether your laptop is fast or slow. It cares about the shape of the growth curve: when you double the input, does the time double, quadruple, or barely move?

The notation drops everything that does not change that shape, from constant factors to the hardware you run on. O(n) means “proportional to n”, whether the real cost is 3n + 7 or 0.001n + 1000000. Make n large enough and only the shape is left.

Big O examples in Python, timed at growing input sizes

Each function below was timed with Python’s timeit module on Python 3.11, at input sizes an order of magnitude (or a doubling) apart.

Constant time: a dictionary lookup

1
2

def dict_lookup(d, key):
    return d[key]

The input grows a thousandfold. The time per call stays flat, within measurement noise. A dict is a hash table: Python computes a hash of the key and jumps straight to the matching bucket, regardless of how many other entries exist. This is O(1), constant time.

Linear time: summing a list

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Each tenfold increase in n brings a roughly tenfold increase in time. The loop touches every element exactly once, so the work scales directly with the input. This is O(n), linear time, and it is where most everyday code lives.

Quadratic time: checking for duplicates the naive way

1
2
3
4
5
6

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

Doubling n roughly quadruples the time at every step. The outer loop runs n times and the inner loop runs close to n times for each outer iteration, so the total work is proportional to n * n. This is O(n^2), quadratic time. It is the class that ruins production code, because it looks fine in a test with 50 rows and times out with 50,000.

Logarithmic time: binary search

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

A thousandfold increase in n barely doubles the time. Each step of the loop throws away half the remaining range, so the number of steps needed grows with log2(n) rather than with n itself: about 10 steps for a thousand items, about 20 for a million. This is O(log n). Git bisect runs the same algorithm over commit history instead of a sorted array: it finds the broken commit among hundreds in a handful of steps because every test discards half of the remaining range.

Linearithmic time: sorting

1

sorted_nums = sorted(nums)

Each tenfold step in n costs more than tenfold in time, but well short of the hundredfold a quadratic algorithm would show. Python’s sorted() uses Timsort, which does O(n log n) comparisons: merging proceeds in roughly log n rounds, and each round touches every one of the n elements once to merge adjacent runs. Every general-purpose sort you will use day to day lands here (Timsort, mergesort, quicksort’s average case), which is why O(n log n) is treated as “as good as sorting gets” rather than compared against O(n).

Common Big O complexity classes, fastest to slowest

Look at the last two rows. Going from O(n log n) to O(n^2) at a million items is the difference between a report that runs in a second and one that is still running when someone kills the process.

What Big O notation leaves out

Big O describes asymptotic growth, meaning what happens as n gets arbitrarily large. Three things fall through that gap.

Constants are invisible. O(n) with a constant factor of 1000 can be slower in practice than O(n^2) with a tiny constant, for every n you will ever see. Big O tells you which curve wins eventually, not which function is faster on your data. That is why insertion sort, which is O(n^2), is still the better choice for very small arrays, and why Timsort uses binary insertion sort to build up each small run to a minimum length (minrun, typically 32-64 elements) before it starts merging runs together.

Small n does not show the curve. The quadratic timings above only became obviously quadratic once n passed a few hundred. At n = 10 almost anything finishes before you notice, which is why a function can clear every test you write locally and still fall over on production data volumes.

Space complexity is a separate axis. dict_lookup, sum_loop, has_duplicate_naive, and binary_search all run in roughly constant extra memory: none of them allocate a second data structure proportional to the input. sorted() does not — it returns a new list the same size as the input, O(n) space, because it never sorts in place. Some algorithms trade memory for speed on purpose: a memoized Fibonacci function stores every result it has already computed, spending O(n) space to turn O(2^n) time into O(n) time. When you state the complexity of a function, say which axis you mean: the faster version is often the one that uses more memory.

How to spot an accidental O(n^2) in your code

The nested loop earlier is the obvious case. The one that reaches production usually has no nested loop in it.

Membership tests inside a loop. x in some_list is O(n) on a list, because Python has to scan it. Running that check inside a loop that already runs n times gives you O(n^2) without a second for in sight:

1
2
3
4
5
6

# O(n^2): "in" scans the whole list on every iteration
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Swap the list for a set, where membership is O(1), and the loop drops to O(n):

1
2
3
4
5
6

# O(n): "in" is a hash lookup
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Rebuilding a list instead of appending to it. result + [item] allocates a new list and copies every existing element into it; result.append(item) grows the existing list in place.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # copies everything built so far, every time
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) amortized
    return result

Building a list of 8,000 items with + took 65 ms. The same list with .append() took 0.15 ms. The gap widens as n grows, because one is quadratic and the other is linear.

The N+1 query. Fetch a list of rows, then loop over them issuing one more query per row for related data, and a single query has become n + 1: O(n) round trips to the database instead of one. An index, as covered in how database indexes work, turns a single lookup from an O(n) table scan into O(log n). It does nothing for a loop that sends a thousand separate queries. The fix has the same shape as the set fix above: replace the per-row operation with one operation done once. Here that means a single query with a join, which SQL JOIN types explained walks through.

How to measure the complexity of your own code

Pick the function you suspect, usually one with a loop whose trip count depends on data size. Time it with timeit at three or four input sizes, each ten times the last, and divide each timing by the previous one. A ratio near 1 is O(1) or O(log n). Near 10 is linear. Somewhere between 10 and 100 is O(n log n), like the 17-21 the sorted() table shows. Near 100 means you have an O(n^2) to hunt down; if that makes the big sizes too slow to wait for, double n instead of multiplying by ten and look for a ratio near 4. Start with the list membership tests and + rebuilds inside that loop, then any query sent once per row.

Related articles

• How to Use Git Bisect to Find a Broken Commit
• How Database Indexes Work and When to Add One
• SQL JOIN Types Explained With Examples