Big-O Notation Explained with Real Code

Your code works on 100 items. Will it still work on 1,000,000? Big-O notation answers that question. It describes how the running time (or memory use) of an algorithm grows as its input gets bigger.

You don't need advanced maths to use it. In this article we'll look at real functions, count the work they do, and build an intuition you can apply to your own code.

The core idea: growth, not speed#

Big-O doesn't tell you that a function takes 3 milliseconds. It tells you how the time scales:

• Double the input of an O(n) function and the time roughly doubles.
• Double the input of an O(n²) function and the time roughly quadruples.

We also drop constants and smaller terms. A function that does 3n + 10 steps is simply O(n), because as n gets large the 3 and the 10 stop mattering compared to the growth itself.

O(1): constant time#

The work doesn't depend on the input size at all:

def get_first(items):
    return items[0]

def is_even(n):
    return n % 2 == 0

Indexing a list, looking up a key in a dictionary and appending to a list (on average) are all O(1).

O(n): linear time#

The work grows in direct proportion to the input. Looping over every item once is the classic example:

def find_max(numbers):
    largest = numbers[0]
    for n in numbers:          # runs n times
        if n > largest:
            largest = n
    return largest

Hidden O(n) operations are worth knowing too: x in some_list, some_list.index(x), sum() and max() all scan the whole list.

O(n²): quadratic time#

A loop inside a loop, where both run over the input, gives you roughly n × n steps:

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

For 1,000 items that's about half a million comparisons. For 1,000,000 items it's about 500 billion. That's the difference between instant and "come back tomorrow".

Fixing it: trade memory for speed#

We can make has_duplicates O(n) by remembering what we've already seen in a set, whose membership checks are O(1) on average:

def has_duplicates(items):
    seen = set()
    for item in items:          # runs n times
        if item in seen:        # O(1) on average
            return True
        seen.add(item)          # O(1) on average
    return False

Or, more concisely:

def has_duplicates(items):
    return len(set(items)) != len(items)

We spend a little extra memory (O(n) space) to save an enormous amount of time. This trade-off is one of the most common optimisations in real-world code.

O(log n): logarithmic time#

Logarithmic algorithms cut the problem in half at every step. Binary search on a sorted list is the textbook example:

def binary_search(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            low = mid + 1       # discard the left half
        else:
            high = mid - 1      # discard the right half
    return -1

Searching 1,000,000 sorted items takes at most about 20 steps, because 2²⁰ ≈ 1,000,000. Double the data and you add just one more step.

O(n log n): the sweet spot for sorting#

Efficient general-purpose sorting algorithms run in O(n log n). That includes merge sort and Timsort, which powers Python's sorted() and list.sort(). It's only slightly worse than linear, and it's the best possible for sorting by comparing elements.

names = sorted(names)   # O(n log n)

Comparing growth rates#

Approximate number of steps for different input sizes:

How to analyse your own code#

1. Find the loops. A loop over the input is usually O(n). Nested loops over the input multiply: O(n²).
2. Look inside function calls. item in my_list inside a loop is a hidden nested loop.
3. Keep the biggest term. O(n² + n) simplifies to O(n²).
4. Think about the worst case. Unless stated otherwise, Big-O usually describes the worst case.

Here's a sneaky example. What's its complexity?

def common_items(a, b):
    return [x for x in a if x in b]

If b is a list, x in b scans it every time, so this is O(n × m). Convert b to a set first and it drops to O(n + m):

def common_items(a, b):
    b_set = set(b)                          # O(m)
    return [x for x in a if x in b_set]     # O(n)

Recap#

• Big-O describes how work grows with input size, ignoring constants.
• Common classes, fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²).
• Nested loops and hidden scans (in on a list) are the usual culprits behind slow code.
• Sets and dictionaries turn O(n) lookups into O(1), which is often the easiest big win.

Next time your code slows down as your data grows, don't reach for a faster server first. Reach for Big-O.