Suppose that there are $n$ phone booths in a region and we wish to visit each of them twice, but not in two consecutive times. Discuss the computational complexity of a naive algorithm for finding an order of visits that minimizes the total travel time.

A naive algorithm is to generate all permutations of $2n$ booths, discard the ones which have at least one booth as consecutive positions (assume the cost of this is 0), and compute the total travel time for the remaining ones. Assuming the time taken to compute total travel time for a given ordering is $2n$ and the number of such permutations is $\frac{(2n)!}{2^n}$ then the total time for the algorithm would be $2n \cdot \frac{(2n)!}{2^n}$.