1

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
  • 1
    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
4

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.