Back to course sections
    Mark As Completed Discussion

    Representation of Space Complexity

    Space complexity is generally represented using big O notation in terms of the size of the input. Big O is a convenient way to let us mathematically express how the space requirements of a program grow with the change in the size of the inputs. Here are a few examples:

    • An algorithm that uses a single variable has a constant space complexity of O(1).
    • A method that requires an array of n elements has a linear space complexity of O(n).
    • Computations using a matrix of size m*n have a space complexity of O(m*n).
    • If a k-dimensional array is used, where each dimension is n, then the algorithm has a space complexity of O(n^k).
    • If you store an entire tree in a program and the tree has a branching factor b and depth n then the space complexity of the program/algorithm is exponential, i.e., O(b^n).

    This way the complexity categorizes algorithms on the basis of their space requirements. The figure below shows the varying space requirements for different categories of space complexity.

    Representation of Space Complexity