O(2^n) and O(n!) complexity?

This is a discussion on O(2^n) and O(n!) complexity? within the C Programming forums, part of the General Programming Boards category; I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know ...

1. O(2^n) and O(n!) complexity?

I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know most of the time recursion takes exponential time but is there any other example can someone give me, also the O(n!) complexity.

2. Notice that these two complexities are generally bad for "an everyday" algorithm and if you come up with an algorithm that has this much time complexity, then you must think twice!

The O(2^n) case.
Assume you want to find all the arrangements of set of n elements! How many are there? 2^n.
So, in order to find them, you need an algorithm of O(2^n) complexity (time).

As for the other case, I do not have anything in mind...

3. Well, after googling, go here. In that table you can find some examples

4. Actually, I think that every recursive algorithm of the form: Τ(n)=nT(n-1), results in O(n!)

5. An obvious example of O(n!), is any algorithm that produces all permutations of n elements since it generates n! permutations. Wiki description of an example algorithm:

permutations_in_lexicographic_order.htm

6. Originally Posted by dotnet13
I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know most of the time recursion takes exponential time but is there any other example can someone give me, also the O(n!) complexity.
The travelling salesman problem is N!. The salesman has to do a tour of N cities, visiting each one only once. So the number of orders is N! (start at a random city, so N choices, visit a random next one, so N-1 chocies, and so on. It's O(N!) rather than N! exactly because a reverse tour is exactly the same distance and, usually, the tour is specified to start and end at the same city.

A simple protein model might treat all residues as either hydrophilic or hydrophobic, and calculate their shapes. (Some people think that evolution started like this, with the RNA code just specifying either "Hydrophobic" or "hydrophilic" amino acids, to create globs of approximately consistent shape). So if we want to calculate a library of N-mers, we need 2^N examples.

7. Malcolm, please check what you say before you say it. Moreover, it would be wise to read the whole thread (it is not that big...) before posting, because you could find what you should check!!!

The travelling salesman problem has complexity O(N!), when it is to be solved via brute force........... Check the link above for more information