\begin{equation} L = \text{SPACE}\qty(\log n) \end{equation}

For time, the gold standard for languages with \(\geq n\) to read input is \(\text{TIME}\qty(n)\) or at best \(\text{TIME}\qty(n^{k})\).

For space, the gold standard for languages with \(\geq n\) characters is \(\text{SPACE}\qty(\log n)\), because to have pointers, store things, etc., will take this much.

additional information

example

Here are some logspace algorithms.

0 and 1

\begin{equation} A = \qty {0^{m}1^{m}: m \in \mathbb{N}} \end{equation}

palendromes

We can solve it by keeping track of length of input, and then check \(x [i] = x[n-i+1]\)

A lottery is a choice problem, where each outcome has a certain probability:

\begin{equation} [S_1:p_1, \dots, S_{n}:p_{n}] \end{equation}

where, \(S_{j}\) has \(p_{j}\) chance of occurring.

utility of a lottery

For a lottery, the utility thereof is the probability of a state happening times the utility of the state:

that is,

\begin{equation} U([S_1:p_1, \dots, S_{n}:p_{n}]) = \sum_{i=1}^{N} p_{i}U(S_{i})} \end{equation}