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.