Derive Savitch's Space Bound

Analyze recursive bounded reachability without charging for the whole recursion tree.

Problem

A configuration graph has $N\le2^{c s(n)}$ vertices, each encoded in $O(s(n))$ bits. Analyze a deterministic recursive test for reachability within $N$ steps and show it uses $O(s(n)^2)$ space.

Hint 1

Test a path of length at most $2^\ell$ by trying each midpoint and making two recursive calls with parameter $\ell-1$.

Hint 2

The two calls and the different midpoint trials run sequentially. Charge one stack frame per recursion depth, not one per recursion-tree node.

Full solution

Define $R(u,v,\ell)$. At $\ell=0$, accept exactly when $u=v$ or one edge leads from $u$ to $v$. Otherwise enumerate each configuration $m$ and accept if both $R(u,m,\ell-1)$ and $R(m,v,\ell-1)$ accept.

An induction proves that $R(u,v,\ell)$ accepts exactly when a path of length at most $2^\ell$ exists: split any such path at its midpoint, and concatenate the two recursively witnessed half-paths in the converse direction.

Choose $\ell=\lceil\log N\rceil=O(s(n))$. One frame stores a constant number of configurations, a midpoint counter, and $\ell$, totaling $O(s(n))$ bits. Memory is reused after each recursive return, so

At depth $O(s(n))$, this gives $S=O(s(n)^2)$.

Checkpoint

The algorithm may take enormous time. Savitch's theorem is a space simulation, and sequential exploration is what keeps space small.

Provenance note

This is an original walkthrough of the standard Savitch recurrence; student submissions are not evidence for correctness.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• Merged summary, pp. 124-127
• Sipser 3e, sec. 8.1
• Arora-Barak draft, sec. 4.2
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: Savitch recursion