Proving correctness of inefficient algorithm - Path between two vertices
If we interpret d/2 as real number division, then A(G,s,t,3) will run forever. If we interpret d/2 as integer division such as 3/2=1, then the algorithm will fail for a graph which is just a path of 6 vertices and 5 edges. If we interpret d/2 rather unnaturally as integer division of d+1 by 2, the algorithm becomes correct but the semantic of A(G,s,t,d) is not very natural either.

Hence, we will change the following part of the algorithm 

              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF


to 

              IF A(G,s,v,d/2) AND A(G,v,t,(d+1)/2) THEN
                   RETURN TRUE
              ENDIF


together with the conventional interpretation of d/2 and (d+1)/2, the integer division.
We will see this change makes the most sense as shown by the simple proposition below that characterizes the semantic of function A(G,s, t,d). 



We have the following proposition.

Reachable(d): A(G,s,t,d) returns TRUE if and only the distance from s to t is less than or equal to d.

Let us prove the above proposition by induction on d.

The base case when d = 1 is trivial.

Suppose reachable(d) is true for all d &lt;= n, where n>=1. Let check the case when d=n+1.  There are two cases.


n+1 is even. Suppose n+1 = 2k. Checking the definition of function A, we can see that A(G,s,t, n+1) returns TRUE if and only if there is a vertex v such that both A(G,s,v, k) and A(G,v,t,k) return true, i.e., both the distance from s to v and the distance from v to t are less than or equal to k, thanks to the induction hypothesis since k &lt;=n. That means the distance from s to t is less than or equal to 2k = n+1.
n+1 is odd. I will leave this case for you to check.


Proof is done.

The correctness of the algorithm is the correctness of reachable(|V(G)|), since there is path from s and t if and only if the distance from s to t is less than or equal to |V(G)|-1 (or |V(G)|, which is equivalent).



To verify that this algorithm can be very inefficient, we should find an example where it runs very slowly.  We would like to choose a graph for which A(G,s,t,d) computes as much as possible and return as late as possible. How about graphs with no edges? Let D be a graph of 2^n vertices without an edge.

Claim: A(D,s,t,2^k) will call A(D,*,*,2^(k-1)) 2^(n+1) times. 

Claim: A(D,s,t,2^n) will call A(D,*,*,1) (2^(n+1))^n=(2^n)^(n+1)=|V(D)|^(log |V(D)| +1) times. 



I will let you contemplate why this algorithm is so inefficient.