2
$\begingroup$

Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage an algorithm needs, i.e. if I have a Turing Machine with three tapes, one for the input, one for the computation, and one for the output, I would like to express the size of each one of them.

Is there a standard way of doing so? If so, is there a reference?

Currently I am using the symbol $\textrm{DATA}$. As an example consider function $list(n) = (1,\dots,n)$. The respective algorithm $List$ for computing the function $list$ is s.t. $\textrm{TIME}(List(n)) \in \mathcal{O}(n)$, since we need to write $n$ symbols, $\textrm{SPACE}(List(n)) = \mathcal{O}(1)$, since we only need to store the current symbol, and $\textrm{DATA}(List(n)) = \mathcal{O}(n)$, since the output is a vector of length $n$.

$\endgroup$
2
$\begingroup$

If your algorithm/TM is called $A$ and the input $x$, it is customary to denote the size of the output by using function and string notation, that is $|A(x)|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.