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

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 nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

Answer 2

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 3

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 4

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 5

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 6

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 7

Any algorithm that calculates all permutation of a given array is O(N!).

Answer 8

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 9

printf("Hello World");

Yes, this is O(n!). If you think it is not, I suggest you read the definition of BigOh.

I only added this answer because of the annoying habit people have to always use BigOh irrespective of what they actually mean.

For instance, I am pretty sure the question intended to ask Theta(n!), at least cn! steps and no more than Cn! steps for some constants c, C > 0, but chose to use O(n!) instead.

Another instance: Quicksort is O(n^2) in the worst case, while technically correct (Even heapsort is O(n^2) in the worst case!), what they actually mean is Quicksort is Omega(n^2) in the worst case.

Answer 10

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 11

In C#

Wouldn't this be O(N!) in space complexity? because, string in C# is immutable.

string reverseString(string orgString) {
    string reversedString = String.Empty;

    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }

    return reversedString;
}

Answer 12

You are right the recursive calls should take exactly n! time. here is a code like to test factorial time for n different values. Inner loop runs for n! time for different values of j, so the complexity of inner loop is Big O(n!)

public static void NFactorialRuntime(int n)
    {
        Console.WriteLine(" N   Fn   N!");
        for (int i = 1; i <= n; i++)  // This loop is just to test n different values
        {
            int f = Fact(i);
            for (int j = 1; j <= f; j++)  // This is Factorial times
            {  ++x; }
            Console.WriteLine(" {0}   {1}   {2}", i, x, f);
            x = 0;
        }
    }

Here are the test result for n = 5, it iterate exactly factorial time.

  N   Fn   N!
  1   1   1
  2   2   2
  3   6   6
  4   24   24
  5   120   120

Exact function with time complexity n!

// Big O(n!)
public static void NFactorialRuntime(int n)
    {
        for (int j = 1; j <= Fact(i); j++) {  ++x; }
        Console.WriteLine(" {0}   {1}   {2}", i, x, f);
    }

Answer 13

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 14

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.

Answer 15

@clocksmith You are absolutely correct. This is not calculating n!. Nor is it of O(n!). I ran it collected the data in the table below. Please compare column 2 and three. (#nF is the # of calls to nFacRuntimeFunc)

n #nF n!

0    0      1
1    1      1
2    4      2
3    15     6
4    65     24
5    325    120
6    1956   720
7    13699  5040

So clearly if performs much worse than O(n!). Below is the a sample code for calculating n! recursively. you will note that its of O(n) order.

int Factorial(int n)
{
   if (n == 1)
      return 1;
   else
      return n * Factorial(n-1);
}

Answer 16

Add to up k function

This is a simple example of a function with complexity O(n!) given an array of int in parameter and an integer k. it returns true if there are two items from the array x+y = k , For example : if tab was [1, 2, 3, 4] and k=6 the returned value would be true because 2+4=6

public boolean addToUpK(int[] tab, int k) {

        boolean response = false;

        for(int i=0; i<tab.length; i++) {

            for(int j=i+1; j<tab.length; j++) {

                if(tab[i]+tab[j]==k) {
                    return true;
                }

            }

        }
        return response;
    }

As a bonus this is a unit test with jUnit, it works fine

@Test
    public void testAddToUpK() {

        DailyCodingProblem daProblem = new DailyCodingProblemImpl();

        int tab[] = {10, 15, 3, 7};
        int k = 17;
        boolean result = true; //expected result because 10+7=17
        assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);

        k = 50;
        result = false; //expected value because there's any two numbers from the list add up to 50
        assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
    }

Answer 17

The simplest example of this is the factorial function:

function factorial(n){
    let fact=1;
    for(var i=1; i<=n;i++){
        fact=fact*i;
    }
    return fact;
}

O(n!)