Python Big-O Notation

Big-O notation is the language programmers use to describe how the running time or memory use of an algorithm grows as its input gets larger. It does not measure exact seconds or bytes — it measures a growth trend, so you can compare two solutions to the same problem and know which one will hold up as your data scales from 100 items to 100 million. Understanding Big-O turns a vague feeling of “this code seems slow” into a precise, testable claim about why, and it is one of the most practical tools you can learn for writing Python that stays fast as it grows.

Overview: How Big-O Notation Works

Big-O describes an upper bound on how the number of operations an algorithm performs grows as a function of the input size, usually called n. It deliberately ignores constant factors and lower-order terms and focuses only on the dominant term as n approaches infinity. For example, an algorithm that performs 3n + 7 operations is written as O(n), because for large n the constants 3 and 7 become irrelevant compared to how the n term itself grows. An algorithm that always performs exactly 1,000,000 steps, no matter the input size, is still O(1) — “constant time” — even though it is not fast in absolute terms, because its cost does not increase as the input grows.

It helps to think of Big-O as counting operations, not seconds. Wall-clock time depends on your CPU, other running processes, and even how Python’s memory allocator happens to behave that day — none of which is a property of the algorithm. Operation count is a property of the algorithm itself, and on real hardware it correlates strongly with actual runtime.

Big-O is technically an upper-bound notation (there are also Ω for lower bounds and Θ for a tight bound), but in everyday programming conversation “Big-O” is used loosely to mean “the growth rate,” and it almost always describes the worst case unless a lesson or docstring says otherwise. A function can have different best-case, average-case, and worst-case complexities — linear search is O(1) best case (the target is first) but O(n) worst case (the target is last or missing), and Big-O conventionally refers to that worst case.

Syntax: Expressing and Reading Big-O

There is no Python syntax for Big-O itself — it is a mathematical notation you write in comments, docstrings, and documentation. The “syntax” to learn is the standard vocabulary of complexity classes, ordered from fastest-growing to slowest:

Notation	Name	Typical example
O(1)	Constant	Dictionary lookup, list indexing by position
O(log n)	Logarithmic	Binary search on a sorted list
O(n)	Linear	Scanning every element once (linear search, sum())
O(n log n)	Linearithmic	Efficient sorting (Python’s sorted() and list.sort())
O(n^2)	Quadratic	Nested loops over the same collection, bubble sort
O(2^n)	Exponential	Naive recursive Fibonacci, generating all subsets
O(n!)	Factorial	Generating all permutations of n items

To read the complexity of a piece of code, apply a few rules of thumb: statements that run one after another add (and you keep only the largest term); a loop nested inside another loop multiplies the complexities; a loop that cuts the problem in half each iteration (like binary search) is O(log n); and a recursive function’s complexity is found by solving its recurrence relation (each call to fib(n-1) and fib(n-2) doubles the work, which is why naive Fibonacci is exponential).

Examples

Example 1: O(1) access vs. O(n) search

Indexing into a list is constant time because Python lists are arrays under the hood, but searching for a value requires checking elements one by one.

def constant_time_access(data: list[int], index: int) -> int:
    return data[index]


def linear_search(data: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    for i, value in enumerate(data):
        comparisons += 1
        if value == target:
            return i, comparisons
    return -1, comparisons


numbers = list(range(1, 11))  # [1, 2, 3, ..., 10]
print(f"Direct access data[5] = {constant_time_access(numbers, 5)}")

index, comparisons = linear_search(numbers, 9)
print(f"Found 9 at index {index} after {comparisons} comparisons")

index, comparisons = linear_search(numbers, 1)
print(f"Found 1 at index {index} after {comparisons} comparisons")

Output:

Direct access data[5] = 6
Found 9 at index 8 after 9 comparisons
Found 1 at index 0 after 1 comparisons

The direct index access always takes exactly one step regardless of list size — that is O(1). Searching for 9 (near the end) took 9 comparisons, while searching for 1 (at the start) took just 1; in the worst case, linear search must inspect every one of the n elements, giving O(n).

Example 2: O(log n) vs. O(n) as input grows

This example counts how many comparisons linear search and binary search actually perform as the list size grows by 10x each time, showing the two growth curves directly instead of just describing them.

def linear_search_count(data: list[int], target: int) -> int:
    count = 0
    for value in data:
        count += 1
        if value == target:
            break
    return count


def binary_search_count(data: list[int], target: int) -> int:
    count = 0
    low, high = 0, len(data) - 1
    while low <= high:
        count += 1
        mid = (low + high) // 2
        if data[mid] == target:
            break
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return count


for size in [10, 100, 1000, 10000]:
    data = list(range(size))
    target = size - 1  # worst case: the value is at the very end
    linear = linear_search_count(data, target)
    binary = binary_search_count(data, target)
    print(f"n={size:>6}: linear={linear:>6}, binary={binary:>3}")

Output:

n=    10: linear=    10, binary=  4
n=   100: linear=   100, binary=  7
n=  1000: linear=  1000, binary= 10
n= 10000: linear= 10000, binary= 14

Notice how dramatically the two columns diverge. Every time the list size multiplies by 10, the linear search’s comparison count also multiplies by 10 — that is what O(n) means. Binary search’s count barely moves (4, 7, 10, 14), because it only grows by roughly log2(n), which is the definition of O(log n).

Example 3: O(n^2) vs. O(n) with a real hidden cost

A very common source of accidental quadratic behavior is checking for duplicates with a nested loop instead of a set.

def has_duplicates_naive(items: list[int]) -> tuple[bool, int]:
    comparisons = 0
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if items[i] == items[j]:
                return True, comparisons
    return False, comparisons


def has_duplicates_fast(items: list[int]) -> tuple[bool, int]:
    seen = set()
    operations = 0
    for item in items:
        operations += 1
        if item in seen:
            return True, operations
        seen.add(item)
    return False, operations


data = list(range(500))  # 500 unique numbers: worst case, no duplicates found

has_dup_naive, naive_ops = has_duplicates_naive(data)
has_dup_fast, fast_ops = has_duplicates_fast(data)

print(f"Naive (O(n^2)) approach: duplicates={has_dup_naive}, comparisons={naive_ops:,}")
print(f"Fast (O(n)) approach:  duplicates={has_dup_fast}, operations={fast_ops:,}")

Output:

Naive (O(n^2)) approach: duplicates=False, comparisons=124,750
Fast (O(n)) approach:  duplicates=False, operations=500

With just 500 items, the nested-loop version performs nearly 125,000 comparisons, while the set-based version performs only 500 operations. That gap is not a fluke of this particular list — it is n(n-1)/2 versus n, and it only gets worse as n grows. At 5,000 items the naive version would need roughly 12.5 million comparisons.

Under the Hood: What Python Actually Does

Big-O in Python is closely tied to how CPython implements its built-in data structures, so it pays to know the complexity of the operations you use constantly:

Operation	list	dict / set
Access by index / key	O(1)	O(1) average
Append / add one item	O(1) amortized	O(1) average
Insert/delete at the front	O(n)	O(1) average (no ordering to shift)
x in obj membership test	O(n)	O(1) average
Sort (sorted(), .sort())	O(n log n)	O(n log n) on keys

A Python list is a dynamic array, not a linked list, so indexing data[i] jumps straight to the right memory address — true O(1) random access. list.append() is O(1) amortized: CPython over-allocates extra capacity when it resizes the underlying array, so most appends just fill unused space, and only occasionally does it need to allocate a bigger array and copy everything over (an O(n) event). Averaged over many appends, the cost per append works out to constant time. By contrast, list.insert(0, x) and list.pop(0) are O(n), because every remaining element has to be physically shifted one slot over in memory.

dict and set are hash tables: Python hashes the key to compute a bucket index directly, giving average-case O(1) lookup, insertion, and deletion — no scanning required. This is why x in some_set is dramatically faster than x in some_list for large collections: the list has to check elements one at a time (O(n)), while the set jumps straight to the bucket (O(1) average). Python’s built-in sorted() and list.sort() use Timsort, a hybrid merge/insertion sort that guarantees O(n log n) in the worst case and drops to O(n) on data that is already mostly sorted.

Common Mistakes

Mistake 1: Using list membership tests inside a loop

Checking item in some_list repeatedly turns an apparently linear loop into a quadratic one, because each membership test itself costs O(n).

def find_common_slow(list_a: list[int], list_b: list[int]) -> list[int]:
    common = []
    for item in list_a:
        if item in list_b:  # O(n) scan on a list, run m times -> O(n * m)
            common.append(item)
    return common


def find_common_fast(list_a: list[int], list_b: list[int]) -> list[int]:
    set_b = set(list_b)  # O(m) to build the set once
    return [item for item in list_a if item in set_b]  # O(1) average lookup -> O(n)


list_a = [1, 2, 3, 4, 5]
list_b = [4, 5, 6, 7, 8]

print(find_common_slow(list_a, list_b))
print(find_common_fast(list_a, list_b))

Output:

[4, 5]
[4, 5]

Both functions return the same result, but find_common_slow costs O(n * m) while find_common_fast costs O(n + m). Converting list_b to a set once, before the loop, is the fix.

Mistake 2: Building strings with repeated concatenation

Strings in Python are immutable, so every += on a string allocates a brand-new string and copies the old contents into it. Doing this inside a loop is a hidden O(n^2).

def build_string_slow(words: list[str]) -> str:
    result = ""
    for word in words:
        result += word + " "  # each += builds a brand-new string: O(n) per call
    return result.strip()


def build_string_fast(words: list[str]) -> str:
    return " ".join(words)  # str.join is O(n) in total, not per call


words = ["Big-O", "describes", "growth", "rate"]

print(build_string_slow(words))
print(build_string_fast(words))

Output:

Big-O describes growth rate
Big-O describes growth rate

Both produce the identical string, but the loop version copies progressively longer strings on every iteration, while str.join() pre-calculates the total length once and builds the result in a single pass.

Other traps to watch for

Beyond these two, watch out for: assuming a lower Big-O class is always faster in absolute terms — for very small n, a simple O(n^2) algorithm with tiny constants can outrun a fancier O(n log n) one with more overhead; and assuming list.insert(0, x) or list.pop(0) behave like append()/pop() — they don’t, and if you need fast operations at both ends of a sequence, use collections.deque instead, which gives O(1) at both ends.

Best Practices

• Choose the data structure that matches your access pattern: use a set or dict when you need fast membership tests or lookups, not a list.
• Use collections.deque instead of a list when you need to push or pop from both ends efficiently.
• Prefer built-in functions and methods (sorted(), sum(), str.join(), comprehensions) over hand-rolled loops — they run in optimized C and have well-documented, predictable complexity.
• Watch for nested loops or repeated in checks on a list inside a loop; both are classic signs of an accidental O(n^2).
• Remember that Big-O describes scalability, not absolute speed — always measure real code with the timeit module on realistic data before optimizing.
• Learn the complexity of the built-in operations you use daily (see the table above); it lets you predict performance problems before you write a single benchmark.
• Don’t over-optimize code that only ever runs on small, fixed-size input — readability usually matters more there than shaving off a constant factor.

Practice Exercises

1. A function contains two separate (not nested) loops, each iterating once over a list of length n. What is the overall Big-O of the function, and why do the two loops not multiply the way nested loops would?
2. Rewrite a function that checks whether two lists share any elements using a nested loop (O(n * m)) so that it runs in O(n + m) instead. Hint: convert one of the lists to a set first, similar to the fix shown in the Common Mistakes section.
3. A naive recursive Fibonacci function, fib(n) = fib(n-1) + fib(n-2), has a time complexity of roughly O(2^n). Explain why, in terms of how many recursive calls are made, and describe how adding memoization (caching previously computed results) would change its complexity class.

Summary

• Big-O notation describes how an algorithm’s running time or memory use grows as its input size n increases, ignoring constants and focusing on the dominant term.
• Common classes, from fastest to slowest growth, include O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), and O(n!).
• In CPython, list indexing and appending are O(1), but inserting/removing at the front is O(n); dict and set give O(1) average lookups, while list membership tests are O(n).
• Hidden quadratic behavior often comes from membership tests or string concatenation inside a loop — both have cheap-looking fixes using set and str.join().
• Big-O measures scalability trends, not absolute speed; always benchmark real code with realistic data before optimizing based on complexity alone.