# Key indicators/determinants that an algorithm has a time complexity of factorial or exponential?

There seems to be significant amount of deep information on the lesser time complexities: linear, polynomial, logarithmic; But there isn't a good source of deep information on how to easily determine if an algorithm is either exponential or factorial time complexity. Usually resources have information on the time complexity of a specific algorithm (eg traveling salesman problem through brute-force search which is `O(n!)`), but no general way to determine if an algorithm is one or the other. Can someone please give specific ways to determine this?

• If one ran a bunch of tests with different amounts of increasing data (10000,20000,30000 data items) and plot the results on a graph one would see whether performance was constant, linear, or exponential as the number of data elements increases. – Jon Raynor May 19 '17 at 17:07
• If it's worse than O(n^3) who cares exactly what it is? It's bad. – candied_orange May 19 '17 at 17:43

An exponential or factorial algorithm is one that's recursive, where the depth of recursion is related to the size of the input, and one of the following holds:

• At each level of recursion the algorithm explores a smaller subset of values than at the level above. This is N!
• At each level of recursion the algorithm explores the same set of values as at the level above. This is M**N, where M is the number of values.

So, an example of a factorial algorithm is producing the permutations of a set of values, where values are not reused:

``````for (v : values)
recurse(list.remove(v))
``````

By comparison, an exponential algorithm one that chooses permutations of values when you can reuse the values:

``````for (v : values)
recurse(count - 1, values)
``````

In the case above, `count` is the depth of recursion. So to find all possible 3-character words formed from the characters 'A' and 'B' you have a depth of 3, which is the exponent or N (you have a base of 2, for the possible characters).