the time required to decide $L$

Question

Suppose that a language $L$ is decided in space $S(n)$ by a DTM with alphabet $\Sigma$ and set of states $\Gamma$. What upper bound can you give for the time required to decide $L$?

Answer 1

A deterministic turing machine with alphabet $\Sigma$ and states $\Gamma$ which uses only $l$ tape cells can only be in $$ N_l = l\cdot|\Sigma|^l\cdot|\Gamma| $$ different configurations (each of the $l$ tape cells contains one element of $\Sigma$, the machine is in one of $|\Gamma|$ states, and the head is positioned over one of the $l$ cells). Thus, if the machine needs $l = S(n)$ tape cells to decide whether a string of length $n$ is in the language, it will do so in no more than $$ T(n) = N_{l} = S(n)\cdot|\Sigma|^{S(n)}\cdot|\Gamma| $$ steps. If it took longer than that, the machine would reach the same configuration twice and hence enter an infinite loop.