98

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.

Improve this question
2
  • rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation Commented Oct 17, 2010 at 12:43
  • 4
    Just 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. Commented Oct 17, 2010 at 14:16

16 Answers 16

Reset to default
151

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); } }
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Given that this is a one-for-one calculation of n!, this is the very definition of O(n!) order of growth.
@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 executed n times and the function in the loop executes (n-1)! steps, then a total of n * (n-1)! = n! steps will be performed. Which is exactly how you proof that this function's time complexity is in Θ(n!).
@Derek Long the loop is O(n), since it is called recursively with (n-1) you get n * (n-1)*(n-2)*...*1 = n! so the function is O(n!).
@AdamRobinson this is not a calculation of n! at all. It's simply a function that executes itself n! times. I also wouldn't call it the "definition" of n! growth. It's just a clear example.
@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.
|
57

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

Improve this answer

3 Comments

I didn't DV, but perhaps it's because it has no sample code, and the big-o notation is not provided...
@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..
Imagine 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.
10

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

Improve this answer

Comments

9

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

Improve this answer

Comments

7

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

alt text
Source: link

Improve this answer

1 Comment

NP 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.
6

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)) {} }
Improve this answer

3 Comments

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++. ;)
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 that next_permutation takes O(1) time on average for this to work.
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.
5

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.

Improve this answer

Comments

4

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?

Improve this answer

Comments

2

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

Improve this answer

Comments

1

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.

Improve this answer

2 Comments

While 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 O-class 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²)
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.
1

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; }
Improve this answer

Comments

1

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); }
Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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); }
Improve this answer

2 Comments

Isn't that O(n^2)?
@Luniam No, It is not because if you could remark the second loop doesn't start from the first index of the array. I don't know if you got what I mean, please reply this comment if you need more explanations!
0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.