Search code examples
algorithmmathtime-complexitycomputer-sciencerecurrence

Solving a complex recurrence relation for the Traveling Salesman

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!

Solution

  • 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)