What is the correct complexity of All paths from Source to Target DFS solution?

Question

The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?

Answer 1

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i < j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i < j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.

Answer 2

For directed graph :-

Suppose there are 7 vertices {0,1,2,3,4,5,6} and consider the worst case where every vertex is connected to every other vertex =>

No of edges required to reach from x to y vertices is as follows :

(6->6) 6 to 6 =0

(5->6) 5 to 6 =1

(4->6) 4 to 6 = (4 to 5 -> 6) + (4 to 6->6) = (1+( 5 -> 6)) + (1+0) =(1 + 1) + 1= 3

(3->6) 3 to 6 =(3 to 4 -> 6) + (3 to 5 -> 6 ) + (3 to 6->6) = (1+3) + (1+1) + (1+0)=7

(2->6) 2 to 6= 4+7+3+1=15

(1->6) 1 to 6= 5+15+7+3+1=31

(0->6) 0 to 6 = 6+5+15+7+3+1=63

So the time complexity to cover all the path to reach from 0 to 6= summation of (1+3+7+15+.....+T(n-1)+T(n))+(Total no of vertices -1) = (2^(n+1)-2-n)+(V-1)

value of n=V-1.

So final time complexity = O(2^V)

For undirected graph :-

Every edge will be traversed twice = 2*((2^(n+1)-2-n)+(V-1))=O(2^(V+1))