Big O Notation in Python: A Complete Guide With Examples

Writing code that works is one thing. Writing code that works efficiently is something else entirely. Big O notation is the standard tool that programmers use to describe how an algorithm's performance scales as the size of its input grows. Whether you are preparing for technical interviews, optimizing a production application, or simply trying to understand why one approach runs faster than another, Big O is an essential concept to master.

This guide walks through every Big O complexity class you are likely to encounter, illustrates each one with real Python code, and then shows how Python's own built-in data structures behave under the hood. By the end, you will be able to look at a piece of Python code and confidently describe its time complexity.

What Is Big O Notation?

Big O notation is a mathematical way of describing the upper bound of an algorithm's growth rate. Instead of measuring exact execution time in milliseconds (which varies by hardware), Big O captures the relationship between input size and the number of operations an algorithm performs.

When we say a function is O(n), we mean that in the worst case, the number of operations grows proportionally to the input size n. Double the input, and you roughly double the work. The notation deliberately ignores constants and lower-order terms because they become irrelevant as the input grows large. An algorithm that takes 3n + 5 steps and one that takes 100n + 2000 steps are both O(n) -- the linear growth rate is what matters.

Here is the formal idea in plain language: given a function f(n) that represents your algorithm's work, we say f(n) is O(g(n)) if there exists a constant c and a starting point n0 such that f(n) <= c * g(n) for all n >= n0. In practice, you rarely need the formal math. You just need to identify which term in your algorithm grows the fastest.

Common Big O Complexity Classes

Below are the complexity classes you will encounter in Python development, ordered from fastest to slowest. Each one includes a practical code example so you can see exactly what that growth pattern looks like.

O(1) -- Constant Time

The algorithm performs the same number of operations regardless of input size. Accessing a list element by index, looking up a dictionary key, or checking the length of a collection are all constant time operations.

# O(1) -- Constant time
def get_first_element(data):
    """Always one operation, no matter how large the list."""
    return data[0] if data else None

my_list = list(range(1_000_000))
result = get_first_element(my_list)  # Instant, even with a million items

O(log n) -- Logarithmic Time

The algorithm cuts the problem in half with each step. Binary search is the classic example. If you have a sorted list of 1,000,000 elements, binary search needs at most about 20 comparisons to find any value.

# O(log n) -- Logarithmic time
def binary_search(sorted_list, target):
    """Halves the search space on every iteration."""
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

data = list(range(0, 1_000_000, 2))  # Even numbers
print(binary_search(data, 482_630))   # Finds it in ~20 steps

O(n) -- Linear Time

The algorithm examines every element once. Finding the maximum value in an unsorted list, summing all elements, or checking whether an item exists in a list (using in) are all linear operations.

# O(n) -- Linear time
def find_maximum(data):
    """Must check every element to guarantee the max."""
    current_max = data[0]
    for value in data:
        if value > current_max:
            current_max = value
    return current_max

numbers = [42, 17, 93, 8, 56, 71, 3, 88]
print(find_maximum(numbers))  # 93

O(n log n) -- Linearithmic Time

This is the sweet spot for efficient sorting algorithms. Python's built-in sorted() function and the list.sort() method both use Timsort, which runs in O(n log n) time. You will also see this complexity in algorithms like merge sort and heapsort.

# O(n log n) -- Linearithmic time
def sort_and_find_median(data):
    """Sorting dominates at O(n log n)."""
    sorted_data = sorted(data)
    mid = len(sorted_data) // 2
    if len(sorted_data) % 2 == 0:
        return (sorted_data[mid - 1] + sorted_data[mid]) / 2
    return sorted_data[mid]

import random
values = [random.randint(1, 10000) for _ in range(100_000)]
median = sort_and_find_median(values)

O(n²) -- Quadratic Time

The algorithm uses a nested loop where both loops iterate over the input. Bubble sort, selection sort, and checking all pairs of elements are common examples. Performance degrades quickly as input grows.

# O(n^2) -- Quadratic time
def has_duplicate_pair(data):
    """Compares every element to every other element."""
    n = len(data)
    for i in range(n):
        for j in range(i + 1, n):
            if data[i] == data[j]:
                return True
    return False

sample = [1, 5, 3, 9, 7, 5]
print(has_duplicate_pair(sample))  # True (5 appears twice)

O(2ⁿ) -- Exponential Time

The work doubles with every additional input element. Recursive algorithms that solve a problem by making two recursive calls per step (without memoization) often fall into this class. The naive recursive Fibonacci implementation is a textbook example.

# O(2^n) -- Exponential time
def fibonacci_naive(n):
    """Each call spawns two more calls. Grows explosively."""
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# fibonacci_naive(30) is noticeably slow
# fibonacci_naive(50) would take an unreasonable amount of time

The fix is memoization or dynamic programming, which reduces the Fibonacci calculation to O(n):

# O(n) -- Linear time with memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_fast(n):
    """Caches results so each value is computed only once."""
    if n <= 1:
        return n
    return fibonacci_fast(n - 1) + fibonacci_fast(n - 2)

print(fibonacci_fast(100))  # Instant: 354224848179261915075

O(n!) -- Factorial Time

The algorithm generates all permutations of the input. This is the slowest practical complexity class. The traveling salesman problem (brute force) and generating all possible orderings of a sequence are factorial-time operations. Even for small inputs, the numbers get staggering: 10 elements produce 3,628,800 permutations, and 20 elements produce over 2.4 quintillion.

# O(n!) -- Factorial time
from itertools import permutations

def brute_force_shortest_route(cities):
    """Tries every possible ordering of cities."""
    shortest = float('inf')
    best_route = None
    for route in permutations(cities):
        distance = calculate_total_distance(route)
        if distance < shortest:
            shortest = distance
            best_route = route
    return best_route, shortest

# Only practical for very small inputs (n < 12 or so)

Big O of Python Built-In Operations

One of the practical benefits of understanding Big O is knowing how Python's own data structures perform. Choosing the wrong data structure can silently turn an O(1) operation into an O(n) one.

List Operations

Python lists are implemented as dynamic arrays. This means index-based access is fast, but inserting or removing elements anywhere other than the end requires shifting elements.

Operation	Example	Time Complexity
Index access	lst[i]	O(1)
Append	lst.append(x)	O(1) amortized
Pop from end	lst.pop()	O(1)
Pop from front	lst.pop(0)	O(n)
Insert at position	lst.insert(i, x)	O(n)
Remove by value	lst.remove(x)	O(n)
Containment check	x in lst	O(n)
Length	len(lst)	O(1)
Sort	lst.sort()	O(n log n)
Slice	lst[a:b]	O(b - a)

Dictionary Operations

Python dictionaries use hash tables internally, which makes key-based operations extremely fast on average. They are the go-to structure when you need quick lookups, insertions, or deletions by key.

Operation	Example	Time Complexity
Get item	d[key]	O(1)
Set item	d[key] = val	O(1)
Delete item	del d[key]	O(1)
Key check	key in d	O(1)
Get keys/values	d.keys()	O(1) view
Iteration	for k in d	O(n)
Length	len(d)	O(1)
Copy	d.copy()	O(n)

One important nuance: while key in d runs in O(1) time, checking whether a value exists with val in d.values() requires iterating the entire dictionary and is O(n). Dictionaries are optimized for key lookups, not value searches.

Set Operations

Sets also use hash tables, giving them O(1) average-case membership checking. This makes them ideal when you need fast containment tests without caring about element order or associated values.

Operation	Example	Time Complexity
Add	s.add(x)	O(1)
Remove	s.remove(x)	O(1)
Containment check	x in s	O(1)
Union	s1 | s2	O(n + m)
Intersection	s1 & s2	O(min(n, m))
Difference	s1 - s2	O(n)

Deque Operations

If you need efficient insertions and removals from both ends of a sequence, the collections.deque is a better choice than a regular list. It is implemented as a doubly-linked list, so adding or removing from either end is O(1). However, accessing an element by index in a deque requires traversal and is O(n).

# deque vs list for front insertions
from collections import deque

# List: inserting at front is O(n) -- shifts all elements
my_list = list(range(100_000))
my_list.insert(0, "new")  # Slow for large lists

# Deque: inserting at front is O(1)
my_deque = deque(range(100_000))
my_deque.appendleft("new")  # Fast regardless of size

How to Analyze Your Own Code

To determine the Big O of a function you have written, follow these steps:

Step 1: Identify the input variable. What is n in your context? It might be the length of a list, the number of rows in a database query, or the number of characters in a string.

Step 2: Count the operations that depend on n. Focus on loops, recursive calls, and any built-in operations that are not O(1). Assignments, comparisons, and arithmetic on fixed-size values are all constant time and can be ignored.

Step 3: Determine how loops nest. A single loop over n elements is O(n). Two nested loops over n elements are O(n^2). A loop that halves the problem each time is O(log n).

Step 4: Combine and simplify. When operations happen sequentially, add their complexities. When they are nested, multiply them. Then drop constants and lower-order terms.

Here is an example that ties it all together:

# What is the Big O of this function?
def process_data(items):
    # Step A: O(n log n) -- sorting
    sorted_items = sorted(items)

    # Step B: O(n) -- single pass
    total = 0
    for item in sorted_items:
        total += item

    # Step C: O(1) -- constant
    average = total / len(sorted_items)

    return average

# Combined: O(n log n) + O(n) + O(1) = O(n log n)
# The sorting step dominates

Common Pitfalls and Practical Tips

Hidden O(n) Inside Loops

One of the easiest mistakes is using an O(n) operation inside a loop without realizing it. The in operator on a list is O(n), so using it inside a loop creates O(n^2) behavior.

# BAD: O(n^2) -- 'in' on a list is O(n), done n times
def find_common_bad(list_a, list_b):
    common = []
    for item in list_a:
        if item in list_b:       # O(n) for each check
            common.append(item)
    return common

# GOOD: O(n) -- convert to set first for O(1) lookups
def find_common_good(list_a, list_b):
    set_b = set(list_b)          # O(n) one-time cost
    common = []
    for item in list_a:
        if item in set_b:        # O(1) for each check
            common.append(item)
    return common

String Concatenation in Loops

Building a string by repeatedly using += inside a loop can be O(n^2) because strings are immutable and each concatenation creates a new string object. Use "".join() instead.

# BAD: O(n^2) due to repeated string creation
def build_string_bad(words):
    result = ""
    for word in words:
        result += word + " "     # New string object each time
    return result.strip()

# GOOD: O(n) -- join handles it efficiently
def build_string_good(words):
    return " ".join(words)

When Big O Does Not Tell the Full Story

Big O describes asymptotic behavior as n approaches infinity. For small inputs, the constant factors that Big O ignores can actually matter more than the growth rate. An O(n^2) algorithm with tiny constant factors might outperform an O(n log n) algorithm with heavy overhead when n is small. In practice, always profile your actual code with realistic data sizes before committing to a more complex algorithm.

Key Takeaways

1. Big O measures growth, not speed. It tells you how performance scales with input size, not how many milliseconds an operation takes. Two algorithms with the same Big O can have very different real-world speeds due to constant factors.
2. Know your data structures. The difference between using a list and a set for membership checks is the difference between O(n) and O(1). Choosing the right data structure is often more impactful than writing a clever algorithm.
3. Watch for hidden complexity. Built-in operations like in, list.insert(), and string concatenation are not always O(1). Nesting an O(n) operation inside a loop silently creates O(n^2) behavior.
4. Simplify by dropping constants. When combining complexities, keep only the fastest-growing term. O(3n^2 + 5n + 100) simplifies to O(n^2).
5. Profile before optimizing. Big O analysis points you in the right direction, but always verify with real measurements. Use timeit and cProfile to confirm that theoretical improvements translate to actual speedups in your specific use case.

Understanding Big O notation transforms the way you think about code. Instead of asking "does this work?" you start asking "does this scale?" -- and that shift in thinking is what separates good Python code from great Python code. Start applying these concepts to your own projects and you will quickly develop an intuition for spotting performance issues before they become problems.