Big-O Notation Explained with Python Examples

When writing software, making code work is only the first step. As datasets grow from a few hundred items to millions of records, inefficient algorithms can cause applications to freeze, time out, or consume excessive memory. To evaluate and compare the performance of algorithms independently of hardware variations, computer scientists use **Big-O Notation**.

Big-O notation describes the upper bound of an algorithm's growth rate—how execution time (**Time Complexity**) or memory consumption (**Space Complexity**) scales as the input size ($n$) increases. This comprehensive guide covers core Big-O complexities, common growth classes, and practical implementations in **Python**.

1. O(1) - Constant Time Complexity

An algorithm is said to run in **Constant Time, O(1)**, if the execution time remains constant regardless of the input size. Accessing a specific element in a Python list by its index or retrieving a value from a dictionary by its key are classic examples.

# O(1) Constant Time Example
def get_first_element(numbers: list) -> int:
    if not numbers:
        return None
    return numbers[0] # Execution takes the exact same time whether list has 5 or 5,000,000 items

2. O(n) - Linear Time Complexity

An algorithm has **Linear Time Complexity, O(n)**, when execution time grows directly and proportionally with the input size ($n$). Traversing an unsorted list in a single loop is a typical O(n) operation.

# O(n) Linear Time Example
def find_maximum(numbers: list) -> int:
    if not numbers:
        return None
    max_val = numbers[0]
    for num in numbers: # Loops through every element once
        if num > max_val:
            max_val = num
    return max_val

3. O(n^2) - Quadratic Time Complexity

An algorithm has **Quadratic Time Complexity, O(n^2)**, when execution time is proportional to the square of the input size. This typically occurs with nested loops iterating over the same dataset, such as naive sorting algorithms (Bubble Sort).

# O(n^2) Quadratic Time Example (Checking for duplicate pairs)
def has_duplicate_pairs(numbers: list) -> bool:
    n = len(numbers)
    for i in range(n):
        for j in range(n):
            if i != j and numbers[i] == numbers[j]:
                return True
    return False

4. O(log n) - Logarithmic Time Complexity

An algorithm has **Logarithmic Time Complexity, O(log n)**, when the problem space is halved with each step. The classic example is **Binary Search**, which operates on sorted collections.

# O(log n) Logarithmic Time Example (Binary Search)
def binary_search(sorted_list: list, target: int) -> int:
    left, right = 0, len(sorted_list) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Conclusion

Mastering Big-O notation enables developers to anticipate performance bottlenecks, choose optimal data structures (like leveraging hash maps for O(1) lookups instead of O(n) linear scans), and write scalable, high-performance Python applications.