Example of O(n!)?

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.

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);
  }
}

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!)).

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!).

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

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

I think I'm a bit late, but I find http://wordaligned.org/articles/next-permutation#tocsnail-sorts-revenge">snailsort</a> 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)) {}
}

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.

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?

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

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;
}

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.

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);
    }

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.

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.

@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);
}

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);
	}

In JavaScript:

// O(n!) Time Complexity

const {performance} = require('perf_hooks');
const t0 = performance.now()
function nFactorialRuntime(input){
  let num = input;
  
  if (input === 0) return 1;

  for(let i=0; i< input; i++){
    num = input * nFactorialRuntime(input-1);
  }
  return num;
}
const t1 = performance.now()
console.log("The function took: " + (t1 - t0) + " milliseconds.")

nFactorialRuntime(5);

for node 8.5+, you need to first include performance from the perf_hooks module. Thank you.