Just part b

Let G = (V, E) be an undirected graph where |V| = n and |E| = m. Suppose for two vertices u, v elementof G, we want to know if u and v are reachable from one another, i.e., if there exists a path in G between u and v. (a) It should be clear that we could use either DFS or BFS to answer this question; however, what is the worst-case space complexity of each of these approaches? Specifically, assume that each vertex is represented using theta (log n) bits. How many bits will you need to store in each algorithm in the worst case? Express your answer asymptotically (i.e., using theta (middot) notation). (b) Let us try to develop a more space-efficient approach. Consider the procedure EXISTS-PATH(a, b, k), which takes as parameters vertices a, b Element V, and returns true if there exists a path in G connecting a and b that has at most k edges; otherwise, it returns false. We can implement this function as follows: For k > 1, EXISTS-PATH(a, b, k) = V_ w Element V (EXISTS-PATH(a, w, [k/2]) Lambda EXISTS-PATH(w, b, k/2)) For k = 1, EXISTS-PATH (a, b, k) = true if and only if (a, b) Element E or a = b; otherwise false. In other words, EXISTS-PATH(a, b, k) returns true if and only if there exists some vertex w Element V such that there is a path from a to w that uses at most [k/21] edges, and a path from w to b that uses at most [k/2] edges. Now, to answer the reachability question for a particular pair of vertices u, v Element V, we simply return the result of EXISTS-PATH(u, v, n-1). First argue that this algorithm is correct. Next, bound the number of bits the algorithm needs to store in the worst case - give your answer in asymptotic notation. (As before, assume that vertices can be represented using Theta (log n) bits.)