Big O Notation Cheat Sheet: Time & Space Complexity Guide

Big O notation describes how an algorithm's performance scales with input size. It's the universal language for comparing algorithm efficiency — ignoring constants and low-order terms to focus on the growth rate that matters.

Quick reference

All complexity classes from fastest to slowest, with everyday examples.

The rule of thumb: for n = 1,000,000, O(1) and O(log n) are instant; O(n) is fast; O(n log n) is acceptable; O(n²) starts to hurt; O(2ⁿ) and O(n!) are infeasible.

Understanding growth rates

Concrete numbers help make this intuitive. Operations for different n values:

O(1) — Constant time

Performance is independent of input size. The fastest possible.

# O(1) examples
def get_first(arr):
    return arr[0]           # Index access — always one step

def lookup(hashmap, key):
    return hashmap[key]     # Hash map lookup — O(1) average

def push(stack, value):
    stack.append(value)     # Push to stack/list end — O(1) amortized

def is_even(n):
    return n % 2 == 0       # Arithmetic — O(1)

// O(1) in JavaScript
const getFirst = arr => arr[0];
const lookup = (map, key) => map.get(key);  // Map.get is O(1)
const peek = stack => stack[stack.length - 1];

O(log n) — Logarithmic time

Input is halved (or divided) each step. Very efficient for large n.

# Binary search — O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Each iteration halves the search space:
# n=1000 → ~10 iterations (log₂ 1000 ≈ 10)
# n=1000000 → ~20 iterations (log₂ 1000000 ≈ 20)

Other O(log n) operations:

• Balanced BST lookup, insert, delete
• Heap push/pop
• bisect.bisect_left() in Python
• Exponentiation by squaring

O(n) — Linear time

One pass through the data. The minimum for problems that require reading all input.

# Linear search — O(n)
def find(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Sum array — O(n)
def total(arr):
    return sum(arr)

# Find max — O(n)
def maximum(arr):
    result = arr[0]
    for val in arr:
        if val > result:
            result = val
    return result

# Count occurrences — O(n)
from collections import Counter
def count_chars(s):
    return Counter(s)   # O(n) where n = len(s)

Key insight: a single loop over n elements is O(n), even with constant-time operations inside.

O(n log n) — Linearithmic time

The lower bound for comparison-based sorting. Typical of divide-and-conquer algorithms.

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

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

# Python's built-in sort (Timsort) is O(n log n)
arr.sort()
sorted_arr = sorted(arr)

O(n²) — Quadratic time

Nested loops over the same data. Acceptable for small n (< 1,000), problematic for large n.

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

# Find all pairs — O(n²)
def all_pairs(arr):
    pairs = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            pairs.append((arr[i], arr[j]))
    return pairs

# Two-sum naive — O(n²)  [the O(n) version uses a hash map]
def two_sum_naive(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]

Spot the pattern: any algorithm with two nested loops that each scale with n is O(n²).

O(2ⁿ) — Exponential time

Doubles with each additional element. Only feasible for very small n (< ~30).

# Naive recursive Fibonacci — O(2ⁿ)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # Two calls, each branching again

# Fix: memoization brings it to O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Generate all subsets — O(2ⁿ)
def all_subsets(arr):
    if not arr:
        return [[]]
    rest = all_subsets(arr[1:])
    return rest + [[arr[0]] + subset for subset in rest]

O(n!) — Factorial time

Grows faster than exponential. Only viable for n ≤ 10–12.

# Generate all permutations — O(n!)
from itertools import permutations

def all_perms(arr):
    return list(permutations(arr))

# Brute-force traveling salesman — O(n!)
def tsp_brute(cities, dist):
    from itertools import permutations
    best = float('inf')
    for perm in permutations(cities):
        cost = sum(dist[perm[i]][perm[i+1]] for i in range(len(perm)-1))
        best = min(best, cost)
    return best

Data structure operations

Time complexity for common data structure operations (average case):

Sorting algorithms

When to use what:

• Small n (< 20): insertion sort (low overhead)
• General purpose: merge sort or built-in sort (Timsort)
• Memory constrained: heap sort
• Nearly sorted data: insertion sort or Timsort
• Integer keys in range: counting or radix sort

Space complexity

Big O also measures memory usage. The same notation applies.

# O(1) space — only uses a fixed number of variables
def sum_array(arr):
    total = 0        # O(1) extra space
    for x in arr:
        total += x
    return total

# O(n) space — stores n elements
def copy_array(arr):
    return arr[:]    # New array of size n

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

# O(log n) space — binary search recursive
def binary_search_rec(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, right)
    else:
        return binary_search_rec(arr, target, left, mid - 1)
# Stack depth = O(log n) since we halve each time

Recognizing complexity from code

Pattern recognition guide:

# O(1): No loops, no recursion relative to n
result = arr[0] + arr[-1]

# O(log n): Input is halved each step
while n > 1:
    n //= 2

# O(n): Single loop through data
for x in arr:
    process(x)

# O(n log n): Sort + linear scan, or divide-and-conquer
arr.sort()           # O(n log n)
for x in arr:        # O(n)
    ...              # total: O(n log n)

# O(n²): Nested loops both over n
for i in range(n):
    for j in range(n):
        ...

# O(n²): Quadratic even with different variables if both scale with n
for i in range(len(arr)):
    for j in range(len(arr)):
        ...

# O(n + m): Two separate loops over different inputs
for x in list_a:    # O(n)
    ...
for y in list_b:    # O(m)
    ...

# O(n * m): Nested loops over different inputs
for x in list_a:
    for y in list_b:
        ...

Amortized complexity

Some operations are occasionally expensive but cheap on average.

# Dynamic array append — O(1) amortized, O(n) worst case
arr = []
for i in range(n):
    arr.append(i)    # Usually O(1), occasionally O(n) when resizing
# Total: O(n) for n appends → O(1) amortized per append

# Hash map operations — O(1) amortized
d = {}
for i in range(n):
    d[i] = i         # O(1) amortized (rare resizing/rehashing)

Common algorithm patterns and their complexity

Optimisation examples

Seeing how to improve complexity:

# BEFORE: O(n²) — check if any two numbers sum to target
def has_pair_naive(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return True
    return False

# AFTER: O(n) — use a hash set
def has_pair_fast(arr, target):
    seen = set()
    for x in arr:
        if target - x in seen:
            return True
        seen.add(x)
    return False


# BEFORE: O(n²) — count duplicates with nested loop
def count_dupes_naive(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                count += 1
    return count

# AFTER: O(n) — use Counter
from collections import Counter
def count_dupes_fast(arr):
    freq = Counter(arr)
    return sum(c * (c - 1) // 2 for c in freq.values())


# BEFORE: O(n) — check membership in list
items = [1, 2, 3, ..., n]
if x in items:   # O(n) scan

# AFTER: O(1) — use set
items_set = set(items)  # O(n) once
if x in items_set:       # O(1) lookup

Common mistakes

Big O, Big Θ, Big Ω

Three related notations that are often confused:

In practice, "Big O" is used loosely to mean "the expected growth rate", not strictly the worst case. Context usually makes this clear.

FAQ

Q: Does Big O account for real-world performance?
No. O(n) with a large constant can be slower than O(n²) for small n. Big O describes asymptotic behaviour (as n → ∞). Always profile real code — the "theoretically better" algorithm isn't always faster in practice.

Q: What's the difference between O(n) and O(2n)?
Nothing — constants are dropped. O(2n) = O(n). Big O only captures the growth rate, not the exact count of operations.

Q: Is O(n + m) the same as O(n)?
Not necessarily. If m can grow independently of n (like processing two separate inputs), keep O(n + m). If m is bounded by n, it simplifies. For example, BFS on a graph is O(V + E), not O(V).

Q: How do I calculate complexity for recursive functions?
Use the recurrence relation and solve with the Master Theorem. T(n) = 2T(n/2) + O(n) → O(n log n) (merge sort). Or draw the recursion tree: depth × work per level.

Q: When should I actually care about Big O?
When n is large enough that growth rate matters. For n < 100, almost anything works. For n > 100,000, O(n²) algorithms become painfully slow. For n > 10,000,000, even O(n log n) needs care.

Q: Is O(log n) always base-2?
The base doesn't matter for Big O — log₂n and log₁₀n differ only by a constant factor. By convention, log in CS usually means log₂, but Big O drops the base.