Big-O notation

Why it matters

Two programs can give the same answer and still behave very differently. One finishes instantly on a list of a million items; the other takes hours. The difference is rarely the computer or the language. It is how much work the algorithm does as the input grows. Big-O notation is the shared vocabulary developers, data scientists and interviewers use to talk about that growth, and it tells you which solution will still work when your data gets ten or a thousand times bigger.

The core idea: count steps, not seconds

Seconds depend on the machine, the language and what else is running. Instead, we count the basic steps an algorithm takes (a comparison, an addition, a lookup) as a function of the input size, called n. Then we keep only the part that dominates when n is large and drop constant factors.

• A loop that does 3 steps per item does 3n steps. That is O(n).
• 3n + 100 is still O(n): for large n the + 100 stops mattering.
• n^2 + n is O(n^2): the square term wins.

Big-O describes the worst case unless someone says otherwise, and it describes shape, not speed. An O(n) loop in slow code can lose to an O(n^2) loop on tiny inputs, but as n grows, the better shape always wins.

The common classes

log n here means log base 2: how many times you can halve n before you reach 1. For a billion items that is only about 30.

Worked example: finding duplicates

Here is a direct way to check whether a list has a repeated value:

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

For each item, it compares against every later item. With n items that is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 comparisons in the worst case (no duplicates). For 4 items that is 6 comparisons; for 1,000 items, 499,500; for 100,000 items, about 5 billion. That is O(n^2).

Now use a set, which can check membership in roughly constant time:

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

One pass, one set lookup and one insert per item: O(n) time. The trade-off is memory: the set can hold up to n items, so it uses O(n) extra space. Trading memory for time like this is one of the most common moves in algorithm design.

Reading Big-O from code

A few rules cover most everyday code:

1. Sequential steps add. A loop over n followed by another loop over n is O(n + n) = O(n).
2. Nested loops multiply. A loop over n inside a loop over n is O(n * n) = O(n^2).
3. Halving gives a log. A loop that cuts the remaining work in half each time is O(log n).
4. Know your built-ins. x in some_list is O(n) (it scans), but x in some_set and d[key] are O(1) on average. some_list.insert(0, x) is O(n) because every element shifts. Sorting with sorted() is O(n log n).

def total_and_max(nums):
    total = sum(nums)      # O(n)
    biggest = max(nums)    # O(n)
    return total, biggest  # overall O(n)

Common mistakes

• Hidden loops. if x in my_list: inside a for loop over the same list looks like one loop but is O(n^2).
• Keeping constants. Writing O(2n) or O(n/2). Both are just O(n).
• Confusing best and worst case. Linear search can find the target on the first try, but its Big-O is still O(n).
• Forgetting space. A fast solution that builds a huge dictionary may not fit in memory.
• Optimising too early. For 20 items, the clearest code is usually best. Big-O matters when inputs grow.

Quick recap

• Big-O describes how work grows with input size n, ignoring constants and smaller terms.
• From best to worst: O(1), O(log n), O(n), O(n log n), O(n^2).
• Nested loops multiply, sequential loops add, halving gives log n.
• A set or dict often turns an O(n^2) search into O(n), at the cost of extra memory.

Try it

Open the Do tab. You will write an O(n) duplicate check with a set and a function that counts how many comparisons the nested-loop version makes, so you can see the quadratic growth in numbers.