What is the space complexity of depth-first search on a graph with V vertices and E edges with respect to the recursion stack?

• A. O(V)
• B. O(E)
• C. O(1)
• D. O(V+E)

Answer: (A)

The main idea here is how the recursion stack grows with the depth of the search path in depth-first search. The stack contains one frame for each level of recursive calls along the current path. In the worst case, that path can include every vertex, so the maximum depth is V. Therefore the space used by the recursion stack is O(V). The number of edges doesn’t affect the stack depth—DFS may examine many edges, but the stack grows only with how deep the current exploration goes. (There may be additional O(V) space for a visited array or the input graph representation, but the stack itself is bounded by V.)