title: Complexity of finding all simple paths using depth first search?
body: <p>Thanks to everyone replying with ideas and alternate solutions. More efficient ways of solving problems are always welcome, as well as reminders to question my assumptions.  That said, I'd like you to ignore for a moment what problem I'm trying to solve with the algorithm, and just help me analyze the big-Oh complexity of my algorithm as I've written it -- an all simple paths in a graph using depth-limited search as described <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/allSimplePaths.html" rel="nofollow noreferrer">here</a>, and implemented <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices/58446#58446">here</a>. Thanks!</p>
  
  <p>Edit: This is homework, but I've already submitted this assignment and I'd just like to know if my answer correct. I get a little confused over Big-O complexity when recursion is involved.  </p>
  
  <hr>
  
  <p>Original question below: </p>
  
  <p>I'm trying to find the complexity of an all-paths search as given by <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/allSimplePaths.html" rel="nofollow noreferrer">this</a> algorithm.
  Given two vertices, I'm finding all simple paths between them using a depth-first search. </p>
  
  <p>I know that the time complexity of DFS is O(V+E) and its space complexity is O(V), and my intuition is that the complexity of an all-paths search will be more than that, but I'm unable to determine what it will be.  </p>
  
  <p>Related SO questions <a href="https://stackoverflow.com/questions/1642139/algorithm-to-find-the-number-of-distinct-paths-in-a-directed-graph">here</a> and <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices">here</a>.  </p>
  
  <p>Update (in response to a comment below): </p>
  
  <p>I'm trying to solve the <a href="http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon/" rel="nofollow noreferrer">six degrees of Kevin Bacon</a> problem. This generally requires finding the lowest degree of separation between a pair of actors, but I have to find ALL degrees of separation (for now, less than 6, but this can change). </p>