https://ide.codingblocks.com/s/386171 - this is the code for traveling salesman problem.
What will be the time complexity of this prog?
Even after memoization ? Could you explain how ?
Hello @nidhigupta847
please read this:
For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based solution. There are at most O(n2n) subproblems, and each one takes linear time to solve. The total running time is therefore O(n22n). The time complexity is much less than O(n!), but still exponential. Space required is also exponential.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.