0

I read about time complexity and how to compute it. But most of the examples are about for loops, and not comes with recursion. Could anyone use this algorithm as an example? I want to know time complexity when it comes with recursion. That algorithm is to find all simple paths between two points. I see somewhere its time complexity is O(n!), am I right? can someone explain me how O(n!) is computed?

Thanks in advance

arslan
  • 2,034
  • 7
  • 34
  • 61
  • 1
    Possible duplicate of [Time complexity of a recursive algorithm](http://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm) – Antony Dao Mar 16 '16 at 06:28
  • 1
    The so-called [master theorem](https://en.wikipedia.org/wiki/Master_theorem) covers the analysis of some typical cases of recursion. – Codor Mar 16 '16 at 07:09
  • @u_seem_surprised. I think you saying is for DFS, here that algorithm to find simple paths. I guess its time complexity is not O(V+E). I guess it is O(N!). I want to know how to conclude its time comlexity – arslan Mar 16 '16 at 09:56
  • @alim Yes, you are right i missed the part where the code does `path.pop();`, thereby enumerating all possible paths. – uSeemSurprised Mar 16 '16 at 10:01

1 Answers1

1

I'll try to take a stab at this. I'm assuming each node is connected to every other node, since I think that would assist me in establishing the worst case situation. Say, we have 5 nodes in a graph [A,B,C,D,E]; so, n=5. In the worst case, each of the n nodes have n-1 neighbors.

How many options do I have to choose the first point? 5.

After picking the first point, how many ways to choose the next point? 4

Do you see a pattern? (Consider the pushing and popping)

Since, you want to consider all the possible points, you must touch each node at least once, for every path consideration.

So, we have n choices to pick the first node, n-1 to pick the second and so on, which results in the n! number of possible paths, so n! "visits" to each node, using an (un-optimized) algorithm.

Debosmit Ray
  • 5,228
  • 2
  • 27
  • 43
  • Great, that is much clear. By the way, what is time complexity of possible optimized version of this algorithm? It seems there are not much to do with that algorithm. – arslan Mar 16 '16 at 15:09
  • @alim What I meant was if you use some sort of a caching mechanism to store sub-paths from nodes. For instance, say you are aware of the sub-path C-D-E. Then, if you already computed this in the instance when you started from A, you don't have to recompute this for B. This was a very rudimentary and inelegant example. But, I guess you will get the idea. – Debosmit Ray Mar 16 '16 at 22:33