Space complexity

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.
Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as formula_1
formula_2 formula_3 formula_4 etc., where is a characteristic of the input influencing space complexity.
Space complexity classes.
Analogously to time complexity classes DTIME(f(n)) and NTIME(f(n)), the complexity classes DSPACE(f(n)) and NSPACE(f(n)) are the sets of languages that are decidable by deterministic (respectively, non-deterministic) Turing machines that use formula_5 space. The complexity classes PSPACE and NPSPACE allow formula_6 to be any polynomial, analogously to P and NP. That is,
and
Relationships between classes.
The space hierarchy theorem states that, for all space-constructible functions formula_9, there exists a problem that can be solved by a machine with formula_9 memory space, but cannot be solved by a machine with asymptotically less than formula_9space.
The following containments between complexity classes hold.
Furthermore, Savitch's theorem gives the reverse containment that if formula_13,
As a direct corollary, formula_15. This result is surprising because it suggests that non-determinism can reduce the space necessary to solve a problem only by a small amount. In contrast, the exponential time hypothesis conjectures that for time complexity, there can be an exponential gap between deterministic and non-deterministic complexity.
The Immerman–Szelepcsényi theorem states that, again for formula_13, formula_17 is closed under complementation. This shows another qualitative difference between time and space complexity classes, as nondeterministic time complexity classes are not believed to be closed under complementation; for instance, it is conjectured that NP ≠ co-NP.
LOGSPACE.
L or LOGSPACE is the set of problems that can be solved by a deterministic Turing machine using only formula_18 memory space with regards to input size. Even a single counter that can index the entire formula_19-bit input requires formula_20 space, so LOGSPACE algorithms can maintain only a constant number of counters or other variables of similar bit complexity.
LOGSPACE and other sub-linear space complexity is useful when processing large data that cannot fit into a computer's RAM. They are related to Streaming algorithms, but only restrict how much memory can be used, while streaming algorithms have further constraints on how the input is fed into the algorithm.
This class also sees use in the field of pseudorandomness and derandomization, where researchers consider the open problem of whether L = RL.
The corresponding nondeterministic space complexity class is NL.