Описание тега space-complexity
The space complexity of an algorithm quantifies the amount of memory taken by an algorithm to run as a function of the size of the input to the problem. The space complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms.
The space complexity of a program (for a given input) is the
number of elementary objects that this program needs to store
during its execution.
This number is computed with respect to the size n of the input
data.
Formally, for an algorithm T and an input x, DSPACE(T, x) denotes the
number of cells used during the (deterministic) computation T(x).
We will note DSPACE(T) = O(f (n)) if DSPACE(T, x) = O(f (n))
with n = |x | (length of x).