About the following algorithm:reach(Vertex s, Vertex t):    if s = t return TRUE    else        for v in Adj(s) do            if reach(v,t) return TRUE        return FALSEWhy 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?
Runtime of a recursive algorithm to find a path in a DAG
algorithms;graph theory;graphs;runtime analysis
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!)$.