Complexity issue

#1

how the complexity of travelling salesman problem is O(n22^n).please tell how to derive it through the recursion relation…and also explain in specific how each case in possible cases (n2^n) is taking linear time to solve

#2

Hey @Rj.25
Please see this https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
If you still have doubts we can discuss it again.

#3

yes i have doubt that how each subproblem is taking lineAR TIME TO solve and how to derive the compleity through recurrence relation

#4

@Rj.25
So basically when you’re at city 1 and total cities are n, you have a choice to go from current city to any other city. There are n-1 such cities or approx n cities. That’s why complexity is linear for a state.

Now at any city 2^n possible bitmasks exist and there are n such cities. Thus DP states become n*2^n. And at each state there are N possible transitions as told above. So total complexity becomes n^2*(2^n)

If your doubt is resolved please mark it as closed.

#5

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.