# Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$.

The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that runs in $s(n)$ space can have as a combination of the number of states, head positions, and contents of the tape, but I do not see how this number is arrived at.

Can someone explain?

Suppose that $M$ is a deterministic Turing machine that runs in space $s(n)$ and halts on all inputs. We show below that $M$ has $U(n) = 2^{O(s(n))}$ many configurations. I claim that if $M$ doesn't halt within $U(n)$ steps, then it never halts; since we assumed that $M$ always halts, this means that it always halts within $U(n)$ steps. To see the claim, let $\sigma_0,\ldots,\sigma_{U(n)}$ be the configurations after $0,\ldots,U(n)$ steps. Since there are only $U(n)$ different configurations but $U(n)+1$ many $\sigma_i$'s, there must be $i<j$ such that $\sigma_i = \sigma_j$. Therefore starting at $\sigma_i$, the machine will repeatedly go through the configurations $\sigma_i,\ldots,\sigma_{j-1}$, and in particular, will never halt.
It remains to count the number of configurations. Suppose that $M$ has $Q$ states, $C$ tapes, and tape alphabet $\Sigma$. We can describe a configuration of $M$ by specifying the state ($Q$ options), the head locations ($s(n)^C$), and the tape contents (at most $|\Sigma|^{Cs(n)}$; in these bounds we used the fact that at most $s(n)$ cells are used in each tape. In total, the number of configurations is at most $$U(n) = Q s(n)^C |\Sigma|^{Cs(n)}.$$ You can show that $U(n) = 2^{O(s(n))}$ using standard manipulations, completing the proof.