Example of O(n!)?

Question

What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.

Answer 1

One classic example is the traveling salesman problem through brute-force search.

If there are N cities, the brute force method will try each and every permutation of these N cities to find which one is cheapest. Now the number of permutations with N cities is N! making it's complexity factorial (O(N!)).

Answer 2

There you go. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function):

void nFac(int n) {
  for(int i=0; i<n; i++) {
    nFac(n-1);
  }
}

Answer 3

the simplest example :)

pseudocode:

input N
calculate N! and store the value in a vaiable NFac - this operation is o(N)
loop from 1 to NFac and output the letter 'z' - this is O(N!)

there you go :)

As a real example - what about generating all the permutations of a set of items?

Answer 4

Finding the determinant with expansion by minors.

Very good explanation here.

# include <cppad/cppad.hpp>
# include <cppad/speed/det_by_minor.hpp>

bool det_by_minor()
{   bool ok = true;

    // dimension of the matrix
    size_t n = 3;

    // construct the determinat object
    CppAD::det_by_minor<double> Det(n);

    double  a[] = {
        1., 2., 3.,  // a[0] a[1] a[2]
        3., 2., 1.,  // a[3] a[4] a[5]
        2., 1., 2.   // a[6] a[7] a[8]
    };
    CPPAD_TEST_VECTOR<double> A(9);
    size_t i;
    for(i = 0; i < 9; i++)
        A[i] = a[i];


    // evaluate the determinant
    double det = Det(A);

    double check;
    check = a[0]*(a[4]*a[8] - a[5]*a[7])
          - a[1]*(a[3]*a[8] - a[5]*a[6])
          + a[2]*(a[3]*a[7] - a[4]*a[6]);

    ok = det == check;

    return ok;
}

Code from here. You will also find the necessary .hpp files there.

Answer 5

There are problems, that are NP-complete(verifiable in nondeterministic polynomial time). Meaning if input scales, then your computation needed to solve the problem increases more then a lot.

Some NP-hard problems are: Hamiltonian path problem( open img ), Travelling salesman problem( open img )
Some NP-complete problems are: Boolean satisfiability problem (Sat.)( open img ), N-puzzle( open img ), Knapsack problem( open img ), Subgraph isomorphism problem( open img ), Subset sum problem( open img ), Clique problem( open img ), Vertex cover problem( open img ), Independent set problem( open img ), Dominating set problem( open img ), Graph coloring problem( open img ),

Source: link 1, link 2

Source: link

Answer 6

See the Orders of common functions section of the Big O Wikipedia article.

According to the article, solving the traveling salesman problem via brute-force search and finding the determinant with expansion by minors are both O(n!).

Answer 7

In Wikipedia

Solving the traveling salesman problem via brute-force search; finding the determinant with expansion by minors.

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

Answer 8

Bogosort is the only "official" one I've encountered that ventures into the O(n!) area. But it's not a guaranteed O(n!) as it's random in nature.

Answer 9

I think I'm a bit late, but I find snailsort to be the best example of O(n!) deterministic algorithm. It basically finds the next permutation of an array until it sorts it.

It looks like this:

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

Answer 10

The recursive method you probably learned for taking the determinant of a matrix (if you took linear algebra) takes O(n!) time. Though I dont particularly feel like coding that all up.