Space Complexity

Constant Space – O(1)

The space used does not increase with input size.

Example: Swapping two variables

def swap(a, b):
    a, b = b, a  # Uses only a fixed amount of space
    return a, b

x, y = 5, 10
print(swap(x, y))  # Output: (10, 5)

Logarithmic Space – O(log n)

Space grows logarithmically, usually seen in recursive algorithms that use divide-and-conquer.

Example: Binary Search (Recursive)

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Base case

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))  # Output: 3

Linear Space – O(n)

Space grows linearly with input size.

Example: Storing results in an array

def create_list(n):
    arr = []  # Extra space grows linearly
    for i in range(n):
        arr.append(i)
    return arr

print(create_list(5))  # Output: [0, 1, 2, 3, 4]

Linearithmic Space – O(n log n)

Space grows at a rate of nlog⁡nn \log nnlogn, often seen in divide-and-conquer sorting algorithms.

Example: Merge Sort (Recursive)

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)

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [5, 2, 9, 1, 5, 6]
print(merge_sort(arr))  # Output: [1, 2, 5, 5, 6, 9]

Quadratic Space – O(n²)

Space grows quadratically with input size.

Example: Storing all pairs in a 2D list

def create_pairs(arr):
    n = len(arr)
    pairs = [[0] * n for _ in range(n)]  # Creates an n×n matrix

    for i in range(n):
        for j in range(n):
            pairs[i][j] = (arr[i], arr[j])

    return pairs

arr = [1, 2, 3]
print(create_pairs(arr))  

Cubic Space – O(n³)

Space grows cubically, often in multi-dimensional problems.

Example: Creating a 3D matrix

def create_3D_matrix(n):
    return [[[0] * n for _ in range(n)] for _ in range(n)]  # n × n × n matrix

matrix = create_3D_matrix(3)
print(len(matrix))  # Output: 3

Exponential Space – O(2ⁿ)

Space doubles with each additional input, often in recursive problems like the Fibonacci sequence.

Example: Fibonacci (Recursive)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))  # Output: 5

Factorial Space – O(n!)

Space grows factorially, often seen in backtracking problems.

Example: Storing all permutations of a string

from itertools import permutations

def generate_permutations(s):
    return list(permutations(s))  # Stores all permutations in memory

print(generate_permutations("abc"))