compute time complexity on recursive function

Question

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

Possible duplicate of Time complexity of a recursive algorithm — Antony Dao
– Antony Dao, Commented Mar 16, 2016 at 6:28
The so-called master theorem covers the analysis of some typical cases of recursion. — Codor
– Codor, Commented Mar 16, 2016 at 7: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
– arslan, Commented Mar 16, 2016 at 9:56
@alim Yes, you are right i missed the part where the code does path.pop();, thereby enumerating all possible paths. — uSeemSurprised
– uSeemSurprised, Commented Mar 16, 2016 at 10:01

Debosmit Ray · Accepted Answer · 2016-03-16 11:54:27Z

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.

answered Mar 16, 2016 at 11:54

Debosmit Ray

5,4332 gold badges31 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

arslan Over a year ago

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.

Debosmit Ray Over a year ago

@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.

Collectives™ on Stack Overflow

compute time complexity on recursive function

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related