Big O Notation Explained

Big O notation describes how the running time (or memory) of some code grows as the input gets bigger. It ignores the constant factors — how fast your machine is, how tight the loop is — and keeps only the shape of the growth. That shape is what decides whether code that works on a thousand items will still work on a million.

The idea#

Suppose a function takes 3n + 20 steps for an input of size n. For n = 10 that is 50 steps; for n = 1,000,000 it is about 3,000,020. At large n the 20 is irrelevant and so, for the purpose of comparing algorithms, is the 3. What matters is that doubling the input roughly doubles the work. That is O(n): linear.

Big O keeps the fastest-growing term and drops its coefficient. It is an upper bound on growth, and it is about large inputs. For ten items, almost anything is fine.

The classes you will meet#

The gap between rows is enormous at scale. For n = 1,000,000: log n is about 20, n log n is about 20 million, and n² is a trillion. The first is instant; the last does not finish.

Each one in code#

# O(1) - the same work however big the list is
def first(items):
    return items[0]

def lookup(prices, name):
    return prices[name]            # dictionaries hash the key straight to a slot


# O(log n) - halve the search space each step
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
        else:
            high = mid - 1
    return -1


# O(n) - touch each item once
def total(items):
    result = 0
    for x in items:
        result += x
    return result


# O(n log n) - the built-in sort
def sort_and_take_top(items, k):
    return sorted(items)[-k:]


# O(n^2) - every item against every other
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


# O(2^n) - every subset
def subsets(items):
    if not items:
        return [[]]
    rest = subsets(items[1:])
    return rest + [[items[0]] + s for s in rest]

Reading code for its complexity#

A few rules cover most real functions:

• A loop over the input is O(n).
• A loop inside a loop, both over the input, is O(n²). Three deep is O(n³).
• Halving each step — binary search, balanced trees — is O(log n).
• Sequential steps add: an O(n) loop followed by an O(n²) loop is O(n²), because the bigger term wins.
• A call inside a loop multiplies: calling an O(n) function n times is O(n²).

The last rule is where hidden quadratics come from. This looks linear and is not:

def remove_seen(items, seen):          # seen is a list
    result = []
    for x in items:                     # n times...
        if x not in seen:               # ...an O(n) scan of a list
            result.append(x)
    return result                       # O(n^2)

Change seen to a set and in becomes O(1), so the whole function becomes O(n). That one-word change is the most common Big O win in everyday code.

Common operations and their cost#

Knowing this table is more useful day to day than knowing any particular algorithm.

Space complexity#

The same notation describes memory. The total function above uses O(1) extra space, one running sum. The subsets function uses O(2ⁿ) space because it builds every subset. Sorting in place is O(1) extra space; sorted() returns a new list and is O(n). Usually time matters more, but on large data, an O(n) copy inside a loop is a memory problem before it is a speed problem.

Big O, big Omega, big Theta#

You will occasionally see the other letters. Big O is an upper bound: the algorithm grows no faster than this. Big Omega is a lower bound. Big Theta means both, a tight bound. In practice, when people say “this is O(n)” they nearly always mean Theta — it grows linearly, no faster and no slower — and the distinction rarely matters outside a theory course. “Small o” is a strictly-less-than version that you can safely ignore until an exam asks.

Where to go next#

• What is an algorithm? — the thing Big O measures.
• Data structures for beginners — why sets and dictionaries are O(1).
• Sets in Python — the one-word fix in practice.