Exhaustive Search Big-O

I am working on some revision at the moment and specifically going over Big-O notation. I have asked a similar question (which dealt with a different algorithm) but am still unsure if I am going the right way about it or not.

The algorithm that I am looking at is Exhaustive Search (aka Brute For开发者_运维知识库ce, I believe) and looks like this:

Input: G- the graph
   n- the current node
   p– the path so far
1) For every edge nm (from n to m) in G do
2)    If m ∉ p then
3)       p = p ∪ {m}
4)       Exhaustive(G, m, p)
5)    End If
6) End For

So far I have come to the result that this algorithm is O(n) - is this correct? I doubt that it is, and would love to know exactly how to go about working it out; what to look for, what exactly it is that I 'count' each time, etc. I understand that the number of operations taking place need to be counted, but is that all that I need to take note of/count?

EDIT: I have learned that this algorithm is, in fact, O((n-1)!) - is this correct and if so, how did this solution come about as I cannot work it out?

Usually (but not always) with graphs, the input size n is the number of nodes in the graph. It's fairly easy to prove to ourselves that the function (let alone the runtime) is called at least n times - a single path through a graph (assuming it's connected, that is, every node is reachable from every other node via some path) will take `n' calls.

To compute running time of recursive functions, an upper bound on the running time will be the number of times the recursive function is called multiplied by the runtime of the function in a single call.

To see that the worst case runtime is O((n-1)!), consider how many paths are in a fully connected graph - you can visit any node directly from any node. Another way of phrasing this is that you can visit the nodes in any order, save the starting state. This is the same as the number of permutations of (n-1) elements. I believe it's actually going to be O(n!), since we are iterating over all edges which takes O(n) for each state on the path (n*(n-1)!). EDIT: More precisely, we can say it's big-omega(N!). See comments for more details.

Sometimes, it's easier to look at what the algorithm computes than the actual code - that is, the cardinality of all the states (more specificity here, paths).