Space requirements for solving True Quantified Boolean Formulas problem I came across this section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any reference.

For a given QBF
$$Q_1x_1Q_2x_2...Q_nx_n\phi(x_1,x_2,...,x_n)$$ 

for each quantifier, the algorithm presented evaluates 

$$ A = Q_2x_2...Q_nx_n\phi(0,x_2,...,x_n)$$ 
$$B = Q_2x_2...Q_nx_n\phi(1,x_2,...,x_n)$$ 

and returns $A\wedge B$ for $Q_1 = \forall$ and $A\lor B$ for $Q_1 = \exists$. The way I work it out the space should be $O(2^n)$ instead of $O(n + \log(n)) = O(n)$. When I solve a QBF on paper, I realize it is not exponential, so something must be terribly wrong with my analysis.

At each step, the new $A$ and $B$ have one quantifier less, but there are twice as many expressions. I assumed that would build up as
$$ 1: n$$
$$ 2 : (n-1) + (n-1) $$
$$ 3 : (n-2) + (n-2) + (n-2) + (n-2) $$
$$ \ldots $$
$$ k : 2^k (n-k) $$

which goes all the way up to $2^{n-1}$ before decreasing to zero. Can anyone provide a pointer on what I am doing wrong, or even better a good reference?

Thanks
The main difference between time and space is that you can reuse space that is not needed anymore.

If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$.  Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives you a linear space requirement.

This fact is explained quite well in standard introductory text books on Complexity Theory.  You can have a look into Sipser's Introduction to the Theory of Computation, for example. On page 332 (3rd edition) he explains the space requirement for SAT, of which QBF is a generalization.