Big O notation explained with examples

What problem Big O solves

Timing a program in seconds tells you about one machine, one language and one input. Big O answers a more useful question: if the input becomes 10 times larger, how much more work does the algorithm do? An algorithm that does 10 times more work scales very differently from one that does 100 times more.

Formally, f(n) is O(g(n)) if there are constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. In plain words, g is an upper bound on the growth of f once n is large enough, ignoring constant factors.

• n is the size of the input: the length of a list, the number of characters in a string, the number of nodes in a graph.
• Time complexity counts basic steps (comparisons, assignments, arithmetic).
• Space complexity counts extra memory used, not counting the input itself.

How to simplify an expression

Count the steps as a function of n, then apply two rules: drop constant factors and keep only the dominant term.

When an algorithm has two independent inputs, keep both: looping over a list of length n and then over a list of length m is O(n + m), and a loop inside a loop is O(n · m). The base of a logarithm does not matter in Big O, because log₂ n and log₁₀ n differ only by a constant factor.

Common complexity classes

A rough guide: on a modern computer, a simple loop can run tens of millions of basic steps per second in Python and much more in compiled languages. So O(n log n) is fine for millions of items, O(n²) becomes slow around tens of thousands, and O(2ⁿ) is hopeless beyond about 40 to 60 items.

Reading complexity from Python code

Look at the loops. A single loop over the input is O(n). A loop nested in another loop over the same input is O(n²). A loop that halves the remaining range each time is O(log n).

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

Library calls have their own cost. x in some_list is O(n), x in some_set is O(1) on average, list.insert(0, x) is O(n) because every element shifts, and sorted() is O(n log n). A loop that calls an O(n) operation n times is O(n²) even though it looks like a single loop.

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

Best, average and worst case

The same algorithm can take different amounts of work on different inputs of the same size, so complexity is often stated for three cases.

When people say only "the complexity of X", they usually mean the worst case, or the average case for hash tables and quicksort. Amortized cost is a fourth idea: appending to a Python list is occasionally O(n) when the list grows its storage, but O(1) on average over many appends.

Big O, Big Omega and Big Theta

Strictly, an O(n) algorithm is also O(n²), because O is only an upper bound. In everyday use, people write Big O but mean the tightest bound they know, which is what Θ expresses.

Common mistakes

• Forgetting the cost of built-in operations, such as in on a list or slicing items[1:], which copies and is O(k) for k copied elements.
• Counting recursive calls wrongly: a function that calls itself twice on n − 1 is O(2ⁿ), not O(n).
• Ignoring space: building a new list of size n, or a recursion of depth n, costs O(n) memory.
• Writing O(2n) or O(n + 5). Both simplify to O(n).