Big O Notation — Time and Space Complexity

What is Big O Notation?

Big O notation describes how the runtime or memory usage of an algorithm grows relative to the input size. It answers: "If I double the input, what happens to the time/memory?"

It focuses on the worst case and dominant terms — we drop constants and lower-order terms.

f(n) = 3n² + 5n + 100  →  O(n²)

Why It Matters

Two solutions can both be "correct" but one might take 1ms and the other 10 minutes on large inputs. Big O helps you reason about this before writing a single line of code.

Common Complexities

O(1) — Constant

Runtime doesn't change regardless of input size.

def get_first(arr):
    return arr[0]  # always one operation

O(log n) — Logarithmic

Input is halved each step. Very efficient.

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

O(n) — Linear

One operation per element.

def find_max(arr):
    max_val = arr[0]
    for num in arr:       # n iterations
        if num > max_val:
            max_val = num
    return max_val

O(n log n) — Linearithmic

Typical of efficient sorting algorithms.

# Merge sort, heap sort, Python's sorted()
sorted_arr = sorted(arr)  # O(n log n)

O(n²) — Quadratic

Nested loops over the same input.

def bubble_sort(arr):
    for i in range(len(arr)):        # n
        for j in range(len(arr)-1):  # n
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

O(2ⁿ) — Exponential

Each step doubles the work. Avoid for large inputs.

def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)  # two recursive calls each time

How to Calculate Big O

Rule 1 — Drop constants

O(2n) → O(n)
O(500) → O(1)

Rule 2 — Drop lower-order terms

O(n² + n) → O(n²)
O(n + log n) → O(n)

Rule 3 — Different inputs = different variables

def func(a, b):
    for x in a:   # O(a)
        print(x)
    for y in b:   # O(b)
        print(y)
# Total: O(a + b), NOT O(n)

Rule 4 — Nested loops multiply

for i in arr:      # O(n)
    for j in arr:  # O(n)
        ...        # O(n²) total

Space Complexity

Space complexity measures extra memory used (not counting the input itself).

def sum_list(arr):
    total = 0          # O(1) space — just one variable
    for n in arr:
        total += n
    return total
 
def double_list(arr):
    result = []        # O(n) space — new list same size as input
    for n in arr:
        result.append(n * 2)
    return result

Cheat Sheet

Key Takeaway

• Big O describes growth rate, not exact time
• Always aim for O(1) or O(log n) where possible
• O(n²) is usually a red flag — look for a better approach
• Space and time complexity are often trade-offs