Example of O(n!)?

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

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

Example of O(n!)?

Solution 1:

Solution 2:

Related

Recent Posts