2
$\begingroup$

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 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?

$\endgroup$
  • $\begingroup$ 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!)$. $\endgroup$ – David Richerby Mar 16 '16 at 21:54
1
$\begingroup$

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!)$.

$\endgroup$
  • $\begingroup$ Why is it $\sum_{k=0}^{n-1} \frac{1}{k!}$ and not $\sum_{k=0}^{n-1} 1$? $\endgroup$ – shinzou Mar 16 '16 at 22:00
  • $\begingroup$ I'm using $(n-1)\cdots(n-k) = (n-1)!/(n-k-1)!$, and replacing $k$ in the second summation by $n-1-k$. $\endgroup$ – Yuval Filmus Mar 16 '16 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.