Foundations

Time & Space Complexity

● Beginner ⏱ 10 min read dsa

Before you can compare algorithms you need a language for expressing how fast they are. Big O notation is that language. It describes how the runtime (or memory usage) of an algorithm scales as the input size n grows toward infinity.

What Is Big O?

Big O notation expresses the upper bound on growth rate. We ignore constant factors and lower-order terms because they become irrelevant at large scales.

💡

Rules of thumb

Drop constants: O(2n) = O(n). Drop lower terms: O(n² + n) = O(n²). Always express Big O in terms of the dominant term.

O(1) — Constant

Execution time does not depend on the input size at all. Array index access is the classic example.

Python

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

def get_last(arr):
    return arr[-1]         # O(1) — index arithmetic, not search

d = {"a": 1, "b": 2}
val = d["a"]               # O(1) average — hash lookup

O(log n) — Logarithmic

Each step halves the problem. Binary search on a sorted array of 1 billion elements takes only ~30 comparisons.

Python

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1      # discard left half
        else:
            high = mid - 1     # discard right half
    return -1
# Each iteration halves search space → O(log n)

O(n) — Linear

Runtime grows proportionally with input size. Visiting every element once is O(n).

Python

def linear_search(arr, target):
    for i, val in enumerate(arr):   # iterate all n elements
        if val == target:
            return i
    return -1
# Worst case: target not present — visits all n elements → O(n)

O(n log n) — Linearithmic

Divide-and-conquer sorting algorithms like merge sort and quicksort (average) run in O(n log n). This is the theoretical minimum for comparison-based sorting.

Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n)
# Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)

O(n²) — Quadratic

Nested loops over the input. Bubble sort and selection sort are O(n²). Doubling input size quadruples the work.

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # outer loop: n iterations
        for j in range(n - 1):  # inner loop: n iterations
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
# n × n comparisons → O(n²)

Space Complexity

Space complexity measures the extra memory an algorithm uses, not counting the input itself (auxiliary space).

Python

# O(1) space — only a few variables regardless of input size
def find_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

# O(n) space — creates new list proportional to input
def double_values(arr):
    return [x * 2 for x in arr]

# O(n) space — recursive call stack depth proportional to input
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Complexity Cheat Sheet

Notation	Name	Example	n=1000 ops
O(1)	Constant	Array access, dict lookup	1
O(log n)	Logarithmic	Binary search, balanced BST ops	~10
O(n)	Linear	Linear search, list traversal	1,000
O(n log n)	Linearithmic	Merge sort, quicksort avg	~10,000
O(n²)	Quadratic	Bubble sort, nested loops	1,000,000
O(2⊃n)	Exponential	Naive recursion (Fibonacci)	Astronomical
O(n!)	Factorial	Permutation generation	Impossible

⚠️

Big O is worst-case by default

When someone says “O(n)” without qualification they usually mean worst-case. Some algorithms have different best-case (Omega) and average-case (Theta) complexities — always clarify which case you’re discussing in interviews.