Example of 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);
}
}
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!).