Determining the difference between n! and algorithm 2 ^ n

Question

I saw some interesting discussions recently discussing whether a given ("hard") problem has at best 2 ^ n or n! known solution.

My question is that, besides the fact that it follows the algorithm and sees the growth rate, is there a heuristic for quickly determining one or the other? I.e. Are there certain rapidly observable properties of an algorithm that make it explicitly one or the other?

Related discussions:

• stack overflow
• http://news.ycombinator.com/item?id=3621555

Answer 1

There is no algorithm that could determine the complexity of a program [in general]. It is part of the stopping problem - you cannot determine if any algorithm will stop or not. [You cannot evaluate if this is Theta(infinity) or something less than it]

Typically, algorithms typically O(n!) Call a recursive call in a loop with a decreasing range, while O(2^n) algorithms call a recursive call twice in each call.

Note Not all algorithms that call a recursive call twice are O(2^n) - quicksort is a good example for the O(nlogn) algorithm, which also calls a recursive call twice.

EDIT: For example:
SAT brute force solution O(2^n) :

 SAT(formula,vars,i): if i == vars.length: return formula.isSatisfied(vars) vars[i] = true temp = SAT(formula,vars,i+1) //first recursive call if (temp == true) return true vars[i] = false return SAT(formula,vars,i+1) //second recursive call 

Find all the permutations: O(n!)

 permutations(source,sol): if (source.length == 0): print sol return for each e in source: sol.append(e) source.remove(e) permutations(source,sol) //recursive call in a loop source.add(e) sol.removeLast() 

Answer 2

As mentioned above, it is theoretically impossible to check whether the algorithm is O (2 ^ n) or O (n!). However, you can use the following heuristics:

• For different values ​​of n, calculate the number of steps, F (n), solve
• Graph n vs log (F (n)) / n
• If it looks like a flat line (or aligns like a flat line), then this is O (2 ^ n)
• If it looks like a strictly increasing function, then it is super exponential
• If it looks more like a graph of x vs log (x), then it is "probably" O (n!)