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

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

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?

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.

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 ), NP-complete problems0(NP-complete problems1), NP-complete problems2(NP-complete problems3), NP-complete problems4(NP-complete problems5), NP-complete problems6(NP-complete problems7), NP-complete problems8(NP-complete problems9), Boolean satisfiability problem (Sat.)0(Boolean satisfiability problem (Sat.)1),

Source: link 1, link 2

Source: link

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

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

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.

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

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.

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

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

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.