CODEWITHSUNDEEP
algorithm
arslan
arslan

Reputation: 2224

compute time complexity on recursive function

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

Upvotes: 0

Views: 88

Answers (1)

Debosmit Ray
Debosmit Ray

Reputation: 5403

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.

Upvotes: 1

Related Questions