Solving a complex recurrence relation for the Traveling Salesman

Question

I need to solve the exact time complexity for the brute force version of the Traveling Salesman using a recurrence relation.

I've worked out the recurrence relation to be as follows: T(n)=T(n-1)*(n-1)+1

But I'm having trouble reducing that that to a closed form of the function, and thus get the exact time complexity. Not for lack of trying either. It's looking like it's coming out as a binomial sequence but my algebra is a bit rusty.

If anyone could help or point me on the right path I would appreciate it.

Thanks!

Answer 1

Here are a few hints :

• define R(n) = T(n)/(n-1)!
• solve the recurrence for R(n)
• express T(n) as a function of R(n)