In Introduction to the Theory of Computation by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):We need to simulate an $f(n)$ space NTM deterministically. A naive  approach is to proceed by trying all the branches of the NTMs  computation, one by one. The simulation needs to keep track of which  branch it is currently trying so that it is able to go on to the next  one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$  steps and each step may be a nondeterministic choice. Exploring the  branches sequentially would require recording all the choices used on  a particular branch in order to be able to find the next branch.  Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our  goal of $O(f^2(n))$ space. (Sipser, Introduction to the Theory of Computation 334)He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c_2$ is reachable from some other configuration $c_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c_1, c_n, t)$ results in two recursive calls $CANYIELD(c_1, c_m, t/2)$ and $CANYIELD(c_m, c_n, t/2)$, and so on until the distance between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.So, there are two questions I have.I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c_m$ is negligible?I don't understand why we need $2^{O(f(n))}$ space in the naive approach. Why can't we forget about branches we've executed, so that we are still using at most the space required to go all the way down one branch?
The crux of Savitch's Theorem
complexity theory;space complexity