Big O Notation

Big O notation describes how the work an algorithm does grows as its input grows. It won't tell you how many milliseconds your code takes, but it tells you whether doubling the data barely changes the wait, doubles it or makes it four times longer, and that is usually what decides whether code copes with real data.

What Big O measures

Big O counts steps as a function of n, the size of the input: the number of items in a list, characters in a string or rows in a table. You write it as O(...) and read it as 'order of'. O(n) means the work grows in proportion to n.

It describes the shape of the growth, not an exact count, so two simplifications always apply:

• Drop the constants. A function that does 3n + 5 steps is O(n). The 3 and the 5 depend on the language and the machine; the growth doesn't.
• Keep only the biggest term. n² + n is O(n²). Once n is large, the n² part dwarfs everything else.

Unless someone says otherwise, a Big O figure describes the worst case: the input that makes the algorithm work hardest. That is the case you have to plan for, because it is the one that turns up in production.

O(1): constant time

An O(1) operation takes the same number of steps however big the input is. Reading the first item of a list is the classic example:

def first_item(items):
    return items[0]

A list of 10 items or 10 million, it is one step. Reading any item by its index works the same way, and looking up a key in a Python dict is O(1) on average.

'Constant' doesn't mean 'one step' or even 'fast'. A function that always does 50 steps is still O(1), because the 50 never grows. What matters is that the input size has no effect on it.

O(n): linear time

An O(n) algorithm does work in step with the input: twice the data, twice the work. Searching an unsorted list is the standard example, because the only way to find something is to check each item in turn:

def find_index(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

You might get lucky and find the target first time, but Big O plans for the worst case: the target is last, or not there at all, and you check all n items. Summing a list, finding its largest value and copying it are all O(n) for the same reason: each one has to visit every item once.

O(n²): quadratic time

O(n²) usually comes from a loop inside a loop over the same data, where every item is compared with every other item. Here is a straightforward way to check a list for duplicates:

def has_duplicate(items):
    n = len(items)
    for i in range(n):
        for j in range(n):
            if i != j and items[i] == items[j]:
                return True
    return False

For each of the n items, the inner loop runs n times, so the worst case is n × n comparisons. Ten items means 100 comparisons; a thousand means a million. That is why quadratic code feels fine in testing and falls over on real data.

A tidier version starts the inner loop at i + 1, so each pair is compared once. That roughly halves the work, to about n²/2, but it is still O(n²): halving is a constant, and constants drop. To change the growth you need a different approach, such as remembering what you have already seen:

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

This is O(n), because checking a set is O(1) on average. The price is memory: the set can grow to hold every item. Trading memory for time like this is one of the most common fixes for slow code.

O(log n): logarithmic time

An O(log n) algorithm throws away half of what is left at every step. The question it answers is 'how many times can I halve n before only one item remains?', and that number grows very slowly: about 10 halvings for 1,000 items, and about 20 for a million.

Binary search is the best-known example. It only works on sorted data, because sorting is what tells you which half to throw away. Look at the middle item: if the target is bigger, it can only be in the right half, so the left half is gone in one step.

Here is binary search looking for 37 among 12 sorted numbers:

In code, two indexes mark the range still in play, and each pass moves one of them past the middle:

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

Python's standard library has this built in as the bisect module. You may see O(log n) written without a base: in Big O the base doesn't matter, because logs in different bases differ only by a constant factor.

How they compare

The gap between these classes is small for tiny inputs and enormous for large ones. O(1) stays at one step and O(n) is simply n, so the interesting columns are the extremes:

From best to worst, the common classes run O(1), O(log n), O(n), O(n log n), O(n²). O(n log n) is where good general-purpose sorting sits, including Python's built-in sorted(), which is why 'sort it first, then binary search' is often a good deal when you will search many times.

Working out the Big O of your code

You rarely need maths to find the Big O of everyday code. A few rules cover most of it:

• Steps in sequence add, then the biggest wins. A loop over the list followed by another loop is O(n + n), which is O(n).
• Nested loops multiply. A loop inside a loop over the same data is O(n × n), or O(n²).
• Different inputs get different letters. Looping over list a inside a loop over list b is O(n × m), not O(n²), when they can be different sizes.
• Look for hidden loops. A single line can loop for you. x in some_list and some_list.index(x) both scan the list, so they are O(n).

That last rule catches people all the time:

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

If b is a list, every x in b scans it, so this is O(n × m). Turn b into a set first with b = set(b) and each check becomes O(1) on average, so the whole function drops to O(n + m).

Common mistakes

• Treating Big O as a speed. It describes how work grows, not how long it takes. For small inputs an O(n²) loop can beat a cleverer algorithm with more overhead. When speed really matters, measure.
• Forgetting the size of your data. O(n²) over 50 items is 2,500 steps, which is nothing. Over a million rows it is a trillion.
• Quoting the best case. Linear search finding the target first time is a lucky run, not O(1).
• Ignoring memory. Space complexity uses the same notation. The set-based duplicate check is faster but uses O(n) extra memory.
• Optimising too early. Readable O(n) code that runs once a day rarely needs to become clever O(log n) code.

Key takeaways

• Big O describes how an algorithm's work grows with input size n, not its exact running time.
• O(1) stays flat, O(log n) halves the problem each step, O(n) makes one pass and O(n²) compares every pair.
• Drop constants and smaller terms; nested loops multiply, and steps in sequence add.
• Binary search gets its O(log n) from sorted data, so it can throw half away each step.
• For small inputs constants can matter more than the class, so measure before optimising.