$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:$\psi(G,s,t,k) :$ $\hspace{1cm}\text{if k == 1: return 1 if there's edge from s to t, else return 0;}$$\hspace{1cm}\text{foreach } v \in V(G) \text{:}$$\hspace{2cm}L=\psi(G,s,v,\lceil{\frac{k}{2}}{\rceil});$$\hspace{2cm}R=\psi(G,v,t,\lfloor{\frac{k}{2}}{\rfloor});$$\hspace{2cm}\text{if L == 1 and R == 1, return 1;}$$\hspace{1cm}\text{return 0;}$The professor said in class that the algorithm takes at most $\mathcal{O}(\log^2n)$ space, where $n$ is the number of vertices. But don't we pass the entire graph each call? I'll expect to see a $|V|+|E|$ factor in the big-oh, or maybe I miss something here.
Showing strong connectivity is in DSPACE((logn)^2)
algorithm analysis;turing machines;space analysis
You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.