Big O Notation

Overview

Big O notation describes how an algorithm's running time or memory use grows relative to the size of its input, n. It ignores constants and focuses on the dominant term so you can compare approaches independently of hardware. Use it to reason about scalability before you ever run the code.

Syntax / Usage

You count the operations that grow with the input and keep only the largest term. Common classes from fastest to slowest are O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n).

# O(1) - constant: one operation regardless of n
def first_item(items):
    return items[0]

# O(n) - linear: work grows with the list length
def contains(items, target):
    for item in items:          # runs n times
        if item == target:
            return True
    return False

# O(n^2) - quadratic: nested loops over the same input
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

Examples

Constant time lookups make dictionaries powerful for membership checks:

# O(1) average lookup instead of O(n) scanning
seen = {"apple", "banana"}
print("apple" in seen)  # near-instant regardless of set size

Linear time summation touches every element exactly once:

# O(n) time, O(1) extra space
def total(numbers):
    running = 0
    for n in numbers:
        running += n
    return running

Common Mistakes

• Confusing best case with worst case; Big O usually describes the worst case.
• Keeping constants or lower-order terms, e.g. writing O(2n + 5) instead of O(n).
• Ignoring space complexity when an algorithm builds large helper structures.
• Assuming O(log n) requires sorted data in every context (it usually does for search).
• Thinking a smaller Big O is always faster for tiny inputs, where constants can dominate.

See Also

algorithms-searching algorithms-sorting algorithms-recursion