Space Complexity

Space complexity refers to the amount of memory used by an algorithm as the input size increases. Like time complexity, space complexity is usually expressed using Big O notation.

For example, if an algorithm uses a fixed amount of memory regardless of the input size, its space complexity is O(1). If the amount of memory used increases linearly with the input size, the space complexity is O(n). And if the amount of memory used increases exponentially with the input size, the space complexity is O(2^n).

It's important to note that space complexity is different from time complexity as it's not only about the amount of memory used by the algorithm but also the amount of memory used by the data structures used to solve the problem.

Space complexity can be caused by different things such as recursion, function calls, and data structures like arrays and linked lists.

It's important to keep in mind that some algorithms have both time and space trade-offs, for example, a sorting algorithm that has a time complexity of O(n log n) may have a space complexity of O(n) and vice versa.

The most common Big O notations for space complexity are:

• O(1) - Constant space complexity: The amount of memory used by the algorithm does not depend on the input size. An example of this is a simple mathematical operation like addition or subtraction.
• O(log n) - Logarithmic space complexity: The amount of memory used by an algorithm that increases logarithmically with the input size.
• O(n) - Linear space complexity: The amount of memory used by the algorithm increases linearly with the input size. An example of this is an array that needs to store n elements.
• O(n log n) - Log-linear space complexity: The amount of memory used by the algorithm increases with the input size, but at a slower rate than linear. An example of this is a sorting algorithm like merge sort that uses an auxiliary array to store the sorted elements.
• O(n^2) - Quadratic space complexity: The amount of memory used by the algorithm increases with the square of the input size. An example of this is a two-dimensional array that needs to store n x n elements.
• O(2^n) - Exponential space complexity: The amount of memory used by the algorithm increases exponentially with the input size. An example of this is a recursive algorithm that uses a call stack to store the function call frames.
• O(n!) - Factorial space complexity: The amount of memory used by the algorithm. Where n is the input to the factorial function. This is because, in the worst case, the function needs to store the result of each multiplication in memory, and the number of multiplications is equal to the input number.

It's important to note that these are just examples, and a specific algorithm can have multiple complexities.

Constant Space Complexity

Constant space complexity is when the amount of memory used by the algorithm does not depend on the size of the input.

Example:

def find_max(arr):
    " Find the maximum value in an array "
    max_val = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

This function iterates through the array and keeps track of the maximum value seen so far. The amount of memory used by this function is constant, regardless of the size of the input array. The function uses a single variable max_val to store the maximum value seen so far, and it does not create any other data structures or variables that depend on the size of the input array. Therefore, this function has a constant space complexity of O(1).

Logarithmic Space Complexity

Logarithmic space complexity is when the amount of memory used by the algorithm increases logarithmically with the size of the input.

Example:

def binary_search(arr, low, high, x):
    " Binary search algorithm "
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid-1, x)
        else:
            return binary_search(arr, mid+1, high, x)
    else:
        return -1

This function recursively divides the input array in half at each step, until it finds the element x or it determines that x is not in the array. The amount of memory used by this function increases logarithmically with the size of the input array, because the function uses a constant amount of memory to store the function call stack, and the maximum depth of the stack is equal to log2(n) where n is the size of the input array. Therefore, this function has a logarithmic space complexity of O(log n).

Linear Space Complexity

Linear space complexity is when the amount of memory used by the algorithm increases linearly with the size of the input.

Example:

def copy_array(arr):
    " Copy an array "
    n = len(arr)
    new_arr = [0] * n
    for i in range(n):
        new_arr[i] = arr[i]
    return new_arr

This function creates a new array of the same size as the input array, and copies each element of the input array to the corresponding position in the new array. The amount of memory used by this function increases linearly with the size of the input array, because the function uses a constant amount of memory to store the new array, and the size of the new array is equal to the size of the input array. Therefore, this function has a linear space complexity of O(n).

Log-Linear Space Complexity

Log-Linear space complexity is when the amount of memory used by the algorithm increases logarithmically with the size of the input and linearly with some other parameters, for example, a logarithmic increase in the number of elements and a linear increase in the size of each element.

Example:

def merge_sort(arr):
    " Merge sort algorithm "
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

This algorithm uses a divide and conquer strategy, it recursively divides the input array into two halves, and sorts each half separately. The amount of memory used by this function increases logarithmically with the size of the input array, because the function uses a constant amount of memory to store the function call stack, and the maximum depth of the stack is equal to the logarithm of the size of the input array. Therefore, this function has a log-linear space complexity of O(n log n) where n is the size of the input array.

Quadratic Space Complexity

Quadratic space complexity is when the amount of memory used by the algorithm increases at a rate of O(n^2) where n is the size of the input

Example:

def nested_loop(arr):
    " Prints all the pairs of elements in the array "
    n = len(arr)
    for i in range(n):
        for j in range(n):
            print(arr[i], arr[j])

This algorithm uses a nested for loop to iterate over all possible pairs of elements in the input array. The amount of memory used by this function increases at a rate of O(n^2) with the size of the input array, because for each element in the array, it stores the element in memory and performs an operation on each pair of elements.

Exponential Space Complexity

Exponential space complexity is when the amount of memory used by the algorithm increases at a rate of O(2^n) where n is the size of the input.

Example:

def generate_subsets(arr):
    " Generate all subsets of a list "
    if not arr:
        return [[]]
    subsets = []
    for subset in generate_subsets(arr[1:]):
        subsets.append(subset)
        subsets.append([arr[0]] + subset)
    return subsets

This algorithm uses a recursive approach to generate all subsets of a given set of n elements. At each recursive call, it generates 2^n subsets, where n is the size of the input set, and each subset is stored in memory. The amount of memory used by this function increases at a rate of O(2^n) with the size of the input set, because it generates 2^n subsets and stores each subset in memory.

Factorial Space Complexity

Factorial space complexity is when the amount of memory used by the algorithm increases at a rate of O(n!) where n is the size of the input.

Example:

def permutations(arr, l, r):
    " Print all the permutations of arr "
    if l == r:
        print(arr)
    else:
        for i in range(l, r+1):
            arr[l], arr[i] = arr[i], arr[l]
            permutations(arr, l+1, r)
            arr[l], arr[i] = arr[i], arr[l]

This algorithm uses a recursive approach to generate all permutations of a given set of n elements. At each recursive call, it generates n! permutations, where n is the size of the input set, and each permutation is stored in memory. The amount of memory used by this function increases at a rate of O(n!) with the size of the input set, because it generates n! permutations and stores each permutation in memory.

Last Update: 05 Dec, 2024