# Runtime of a recursive algorithm to find a path in a DAG

reach(Vertex s, Vertex t):
if s = t return TRUE
else
if reach(v,t) return TRUE
return FALSE


Why can we say that its runtime on a directed acyclic graph is $O(n!)$?

I can see why there are $n!$ different paths in the graph, is it because in each of those $n!$ paths, the loop will run at most $n$ times?

• If the loop would run at most $n$ times for each of $n!$ paths, you'd only have demonstrated that the running time is $O(n\,n!)$. – David Richerby Mar 16 '16 at 21:54

If you take each recursive call and trace it back to the original call reach(s,t) then you get some directed path starting at $s$. Hence the running time of the algorithm is $\Theta(N)$, where $N$ is the number of directed path starting at $s$ in which $t$ is not an internal vertex.
The number of paths of length $k$ (containing $k$ edges) is at most $(n-1)(n-2)\cdots(n-k)$, since each such path consists of distinct vertices different from $s$ (here we use the DAG property). Since paths have length between $0$ and $n-1$, we get that $$N \leq \sum_{k=0}^{n-1} (n-1)\cdots(n-k) = (n-1)! \sum_{k=0}^{n-1} \frac{1}{k!} \leq e(n-1)!.$$ In particular, $N = O(n!)$.
• Why is it $\sum_{k=0}^{n-1} \frac{1}{k!}$ and not $\sum_{k=0}^{n-1} 1$? – shinzou Mar 16 '16 at 22:00
• I'm using $(n-1)\cdots(n-k) = (n-1)!/(n-k-1)!$, and replacing $k$ in the second summation by $n-1-k$. – Yuval Filmus Mar 16 '16 at 22:01