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 RaynorCommented May 19, 2017 at 17:07
-
1If it's worse than O(n^3) who cares exactly what it is? It's bad.– candied_orangeCommented May 19, 2017 at 17:43
Add a comment
|
1 Answer
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).
