# TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch’s not?

So this is a question pertaining to the proof for $$PSPACE-COMPLETE$$ (for TQBF for example). The idea is to first prove the $$L$$ $$is$$ $$PSPACE$$(easy part) and next is to prove $$PSPACE-COMPLETE$$. The latter requires demonstrating an algorithm which computes the L in polynomial space. This is usually achieved by having recursive calls such that is re-used.

In TBQF proof, the equation $$\phi_{i+1}(A,B)$$= $$\exists Z [\phi_{i+1}(A,Z) \land \phi_{i+1}(Z,B) ]$$ ($$Z$$ is mid-point )is default recursive relation for computing TBQF truth. In any standard proof, it is said that $$\phi_{i+1}(A,B)$$ is computed two times and for $$m$$ nodes, this formula explodes hence, other recursive-relation should be used to bound.

However in Savitch’s proof, the recursive relation is $$Path(a,b,t)$$ = $$Path(a,mid,t-1)$$ AND $$Path(mid,b,t-1)$$ accepts then ACCEPT. In proof, it is stated that this relation reuses-spaces.

My Question is Why in TBQF relation space explodes while in Path, it is reused? Both of these relations looks more or less same to me because both refers to i-1 instances and will need space to store them?.