Big O Notation

It's not necessarily about performance, but rather about scalability.

Big O describes the upper bound of how the runtime or memory grows relative to the input size n. It answers: what happens as n → ∞?

Complexity order (best → worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Simplification rules

1. Drop constants — O(2n) → O(n)
2. Drop non-dominant terms — O(n² + n) → O(n²)
3. Always adopt the pessimistic (worst-case) outlook — e.g. a search that finds the target on the first try is still O(n) by Big O convention

Time complexity

How the number of operations grows with input size.

# O(n): iterating once over a list
for item in arr:
    print(item)

# O(n²): nested loops over the same list
for i in arr:
    for j in arr:
        print(i, j)

Space complexity

How the memory usage grows with input size. Includes auxiliary space (extra allocations), not just the input itself.

# O(1) space — no extra allocation that grows with n
def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total

# O(n) space — creating a new list proportional to n
def double(arr):
    return [x * 2 for x in arr]

# O(n) space — call stack depth in recursion
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)

O(1) — Constant

Runtime does not change regardless of input size.

arr[0]          # array index access
my_dict["key"]  # hash map lookup
arr.append(x)   # append to end of list

O(n) — Linear

One pass through the input. Every element is visited once.

def find(arr, target):
    for item in arr:       # worst case: scans every element
        if item == target:
            return True
    return False

O(log n) — Binary Search

Halves the search space on each step. Input must be sorted.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Each iteration eliminates half the remaining elements → log₂(n) steps.

O(n log n) — Sorting / Divide and Conquer

Split the problem into halves (log n levels), then do O(n) work at each level.

Examples: merge sort, quicksort (average), heapsort

# Merge sort: split + merge
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)   # O(n) merge at each of O(log n) levels

sorted() and .sort() in Python use Timsort → O(n log n).

O(n²) — Quadratic

Nested loops over the same input. Grows fast — avoid for large n.

# Bubble sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):    # inner loop = O(n) per outer step
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Also: selection sort, insertion sort (worst case), naive duplicate detection.

O(2ⁿ) — Exponential

Each step doubles the work. Classic sign: recursive calls that branch twice.

# Naive Fibonacci — recalculates the same subproblems repeatedly
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)  # 2 calls per level → 2ⁿ total calls

Fix with memoization → drops to O(n).

O(n!) — Factorial

Generates all permutations of the input. Unusable beyond ~12 elements.

from itertools import permutations
list(permutations([1, 2, 3, 4]))  # 4! = 24 permutations

Quick reference