Big-O explained simply

When I first heard about Big-O it sounded intimidating, but it turned out to be a simple idea once I saw a few examples. Here's how it finally clicked for me.

What does Big-O measure?

Big-O is used to describe the efficiency of a program, specifically, how the amount of work grows as the input gets bigger. Let's look at an example:

def first(items: list[Any]) -> Any:
    return items[0]

This function takes a list of any type and returns the first item. Whether the list has 1 item, 10 items, or 1,000,000 items, there's only ever one step - just grabbing the first item. That's O(1) - constant time. The work doesn't grow at all, even as the list grows.

Let's look at another example:

def count(items: list[Any]) -> int:
    total = 0
    for i in items:
        total += 1
    return total

This function takes in a list and returns the number of items in it, by going through every item (with the for loop) and adding 1 to the total for each one. So if there's 1 item, the loop runs once. If there are 10 items, it runs 10 times. If there are 1,000,000 items, it runs 1,000,000 times. As the list grows, the number of steps grows with it. The function's efficiency is directly dependent on the size of the list (n), so its Big-O is O(n) - linear time.

Now a cleverer one. Suppose we have a phonebook sorted in alphabetical order and we want to find a particular name. One method: go to the middle page. If it's not the right name, throw away half the pages and look at the other half. Then look in the middle of the new half and do the same. Keep repeating until you find the name.

At each step we throw away half of what's left to search. So a phonebook with 8 names takes 3 steps to find the name, a phonebook with 1024 names takes only 10 steps. This "halving" pattern is called O(log n) - log base 2 of n. It's incredibly efficient: even a phonebook with a billion names would take only about 30 steps.

So to summarise the three so far:

• O(1) - the work never grows (grab the first item).
• O(n) - the work grows in step with the input (look at every item).
• O(log n) - the work grows very slowly, because each step halves what's left (the phonebook search).

Searching a list vs a set

This is where Big-O stops being theory and starts mattering in real code. Let's compare two versions of the same function.

The list

def has_duplicates_v1(items: list[Any]) -> bool:
    already_seen: list[Any] = []
    for i in items:
        if i not in already_seen:
            already_seen.append(i)
        else:
            return True
    return False

This function takes a list and asks whether it has any duplicates. It goes through each item and asks "is this item in the already_seen list?" If not, it adds it, to note we've seen it. If it is already there, we return True - a duplicate exists. If we get through the whole list without ever returning True, we return False, because there are no duplicates.

Here's the catch. When the function asks if i not in already_seen, it has to go through the entire already_seen list from start to finish, checking each item against i. That check alone is O(n). And it happens inside a for loop that itself goes through every item in the list - another O(n). So for every item in the list, we scan the whole already_seen list. That's n × n, which gives us O(n²).

The set

Now the same function with one change:

def has_duplicates_v2(items: list[Any]) -> bool:
    already_seen: set[Any] = set()
    for i in items:
        if i not in already_seen:
            already_seen.add(i)
        else:
            return True
    return False

The only difference is that already_seen is now a set instead of a list. The powerful thing about a set is that checking whether something is in it has constant lookup time - O(1). It doesn't scan from start to finish, it instantly checks whether the item is there. So now we have O(n) for the for loop, times O(1) for the set check, which gives us O(n).

I actually timed both versions on a list of 20,000 items: the list version took about 1.1 seconds, and the set version took about 0.001 seconds - over a thousand times faster. Same logic, one word changed.

So the takeaway: whenever you need to check if an item is present, reach for a set, not a list. It's one of the simplest changes you can make, and the difference is enormous as your data grows.