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 ofO(n)
. - Computations using a matrix of size
m*n
have a space complexity ofO(m*n)
. - If a
k-dimensional
array is used, where each dimension isn
, then the algorithm has a space complexity ofO(n^k)
. - If you store an entire tree in a program and the tree has a branching factor
b
and depthn
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.
