Example of a factorial time algorithm O( n! )

Question

I'm studying time complexity in school and our main focus seems to be on polynomial time O(n^c) algorithms and quasi-linear time O(nlog(n)) algorithms with the occasional exponential time O(c^n) algorithm as an example of run-time perspective. However, dealing with larger time complexities was never covered.

I would like to see an example problem with an algorithmic solution that runs in factorial time O(n!). The algorithm may be a naive approach to solve a problem but cannot be artificially bloated to run in factorial time.

Extra street-cred if the factorial time algorithm is the best known algorithm to solve the problem.

Answer 1

Here is a simple example with Big O( n! ):

This is in python 3.4

 def factorial(n):
    for each in range(n):
        print(n)
        factorial(n-1)

Answer 2

List all permutations of an array is O(n!). Below is a recursive implementation using the swap method. The recursion is inside the for loop and the elements in the array are swapped in position until no more elements remain. As you can see from the result count, the number of elements in the array is n!. Each permutation is an operation and there are n! operations.

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!

Answer 3

Traveling Salesman has a naive solution that's O(n!), but it has a dynamic programming solution that's O(n^2 * 2^n)

Answer 4

Generate all the permutations of a list

You have n! lists, so you cannot achieve better efficiency than O(n!).