What Is Big O Notation? Algorithm Complexity Explained

Big O notation is a way to describe how the cost of an algorithm grows as its input gets larger. Instead of measuring runtime in seconds — which depends on your hardware, language, and mood of the CPU — Big O measures the shape of the growth: if you double the input, does the work double, quadruple, or barely move? That shape is what determines whether code that feels instant on a hundred items grinds to a halt on a million.

The notation intentionally throws away detail. It ignores constant factors and lower-order terms, keeping only the dominant one, because those are what dominate at scale. An algorithm that takes 3n + 50 steps and one that takes n steps are both O(n) — linear — because as n grows, the 3 and the 50 stop mattering. Big O is about the trend, not the exact count.

Why we drop the constants

Say you have two ways to process a list. Method A runs 100n operations; method B runs n². For small inputs, method B looks faster — at n = 10, that’s 1,000 versus 100. But at n = 10,000, method A does a million operations and method B does a hundred million. The n² curve overtakes and never looks back.

Big O captures exactly this crossover behavior. We write method A as O(n) and method B as O(n²) and immediately know that A wins once inputs get large enough. The constant 100 is real, and it matters in practice for small n, but it doesn’t change the fundamental scaling story. Optimizing constants is worthwhile; changing the complexity class is transformative.

The complexity classes you’ll actually meet

Ordered from best to worst, here are the growth rates that show up constantly in real code:

• O(1) — constant. The work doesn’t depend on input size at all. Looking up a value in a hash table, reading an array element by index, or pushing onto a stack. This is the gold standard. It’s why an in-memory key-value store like the ones behind Redis and Memcached can serve reads in sub-millisecond time regardless of how many keys it holds.
• O(log n) — logarithmic. Each step eliminates a large fraction of the remaining work. Binary search halves the search space every comparison; balanced-tree operations behave the same way. Doubling the input adds just one extra step. This is the magic behind database indexing: a B-tree index turns a full-table scan into a handful of comparisons.
• O(n) — linear. You touch each element once. Summing a list, finding a maximum, filtering. Double the input, double the work — predictable and usually fine.
• O(n log n) — linearithmic. The best you can do for general-purpose comparison sorting. Merge sort and the sorts built into most standard libraries live here. It’s linear with a modest logarithmic penalty, and in practice it feels close to linear.
• O(n²) — quadratic. Nested loops over the same data: comparing every item to every other item, naive duplicate detection, bubble sort. Fine for hundreds of items, painful for hundreds of thousands.
• O(2ⁿ) and O(n!) — exponential and factorial. The work explodes. Trying every subset, or every ordering, of the input. These show up in brute-force approaches to hard problems and are only usable for tiny inputs.

A concrete example

Consider checking whether a list contains any duplicates. The obvious approach compares each element to every element after it:

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

Two nested loops over the same list make this O(n²). For a list of 100,000 items that’s up to five billion comparisons — effectively unusable.

Now use a set instead:

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

A single loop, and each set membership check is O(1) on average. The whole function is O(n). Same result, but the second version stays fast at any realistic size. That’s the entire value of thinking in Big O: it tells you before you ship which version falls over. This kind of hash-based lookup is exactly why sets and dictionaries are so central in Python and most other languages.

Time complexity isn’t the whole story

Big O also describes space complexity — how much extra memory an algorithm needs as input grows. The set-based duplicate check above is faster in time but uses O(n) extra memory to hold the seen set, while the nested-loop version uses O(1) extra space. That’s a classic time-versus-space trade-off, and it’s the same trade-off behind caching: spend memory to store results so you don’t recompute them, trading space for time.

A few more nuances worth knowing:

• Best, average, and worst case can differ. Hash-table lookups are O(1) on average but O(n) in a pathological worst case with many collisions. When people quote a single Big O, they usually mean average or worst case — it’s worth being clear which.
• Big O is an upper bound. There are related notations — Big Omega for lower bounds, Big Theta for tight bounds — but in everyday engineering, “Big O” is used loosely to mean “how this scales.”
• Constants still matter in practice. An O(n) algorithm with a huge constant can lose to an O(n log n) one at realistic sizes. Big O tells you the asymptotic winner, not always the practical one. Profile before assuming.

Why it matters day to day

You rarely calculate Big O formally at work. What you do is develop an instinct: this nested loop over the users table is quadratic — will it hold up at ten times the data? That instinct is what separates code that scales from code that quietly becomes a production incident. The same reasoning drives infrastructure decisions like database indexing and query design in systems like PostgreSQL, where the difference between an indexed lookup and a full scan is the difference between O(log n) and O(n) on a table with millions of rows.

The takeaway

Big O notation strips an algorithm down to how it scales — dropping constants and lower-order terms to reveal the dominant growth rate. Memorize the ladder from O(1) up through O(n²) and beyond, learn to spot which rung your code sits on, and you’ll catch the changes that actually matter: not shaving a constant factor, but moving from a quadratic loop to a linear one before real data makes the difference impossible to ignore.