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.

robbell.net/2009/06/abeginnersguidetobigonotation– Charlie CollinsOct 17 '10 at 12:43

4Just to be pedantic, you mean Ω(n!) [lower bound on asymptotic growth] or "time proportional to n!" [upper and lower], not O(n!) [upper bound on asymptotic growth]. Since O(n!) is only the upper bound, lots of algorithms are O(n!) in uninteresting way, because they're O(n) or O(n log n) or O(1) or something like that.– jacobmOct 17 '10 at 14:16
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(n1);
}
}

39Given that this is a oneforone calculation of n!, this is the very definition of O(n!) order of growth. Oct 17 '10 at 12:51

1On a second thought, will the recursive method nFac affect the time complexity of this algorithm? Oct 18 '10 at 3:54

2@Derek: It's definitely
O(n!)
(and more importantlyΘ(n!)
). And yes, the time complexity of a function called in a loop affects the time complexity of the loop. If the loop is executedn
times and the function in the loop executes(n1)!
steps, then a total ofn * (n1)! = n!
steps will be performed. Which is exactly how you proof that this function's time complexity is inΘ(n!)
.– sepp2kOct 18 '10 at 10:24 
5@Derek Long the loop is O(n), since it is called recursively with (n1) you get n * (n1)*(n2)*...*1 = n! so the function is O(n!).– josefxOct 18 '10 at 10:43

2@AdamRobinson Even though upvoted, your comment is completely wrong. Calculation of n! takes just O(n) time  a for loop with multiplication. Similarly, calculation of n2 won't take an O(n2) time  it will be O(1), a single multiplication.– defhltAug 1 '17 at 8:15
One classic example is the traveling salesman problem through bruteforce 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!)
).

I didn't DV, but perhaps it's because it has no sample code, and the bigo notation is not provided...– aioobeOct 17 '10 at 12:49

7@aioobe: since the question is "What's an O(n!) problem" and the answer is "here's one", I wouldn't think you have to say O(n!) explicitly..– ClaudiuOct 17 '10 at 14:22

2Imagine 3 cities. To check any potential route, you have to check the distance between two cities twice. A>B and B> C. You have to start from all 3 corners. Sum the distance onto the first city, so in total that's 3 checks, then sum the distance from the 2nd city onto the 3rd for a total of 6 checks. that's 3! = 6. Do this for 4 cities and the checks become 24. May 15 '12 at 15:49
See the Orders of common functions section of the Big O Wikipedia article.
According to the article, solving the traveling salesman problem via bruteforce search and finding the determinant with expansion by minors are both O(n!).
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)) {}
}

Since n! can be defined as the number of ways to permute a list of n objects, this is my favorite example, although pseudo code would be better than c++. ;) Oct 24 '15 at 0:19

It's not at all obvious this takes O(n!) time.
next_permutation
takes linear time, so a naive computation gives O(n*n!) time (which is strictly greater than O(n!)). You have to argue thatnext_permutation
takes O(1) time on average for this to work. Dec 17 '16 at 21:38 
It's worth noting that this works because
next_permutation
returns the lexicographically next permutation and returns true, or returns the smallest one (which is the sorted permutation) and returns false if a next permutation doesn't exist. Jul 31 '17 at 18:47
There are problems, that are NPcomplete
(verifiable in nondeterministic polynomial time). Meaning if input scales, then your computation needed to solve the problem increases more then a lot.
Some NPhard
problems are: Hamiltonian path problem( open img ), Travelling salesman problem( open img )
Some NPcomplete
problems are: Boolean satisfiability problem (Sat.)( open img ), Npuzzle( 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

5NP stands for Nondeterministic Polynomial, meaning faster than exponential time (but only in theory). Factorial is slower than exponential, in theory and practice. So, this is totally irrelevant. Oct 18 '10 at 6:39
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 bruteforce search; finding the determinant with expansion by minors.
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
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
.

1While mathematically true, O(n) notation is used loosely almost all the time, even by those that do know better. In particular, it is considered deceptive to use a higher Oclass than strictly necessary; so no practitioner will ever refer to an O(n) algorithm as being O(n²), although any algorithm that is in O(n) is also (by definition) in O(n²)– tucuxiFeb 3 '17 at 10:41

This seems more appropriate as a comment than an answer, since it's merely pointing out a technicality in the question and clearly misses the point of what was asked. Jul 31 '17 at 18:42
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;
}
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(n1);
}
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(input1);
}
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.