La complejidad computacional de un algoritmo del camino más largo con un método recursivo

Question

I escribió un segmento de código para determinar la ruta más larga en un gráfico. Lo que sigue es el código. Pero no sé cómo conseguir la complejidad computacional en ella debido al método recursivo en el medio. Dado que encontrar el camino más largo es un problema NP completo supongo que es algo así como O(n!) o O(2^n), pero ¿cómo puedo determinar realmente él?

public static int longestPath(int A) {
    int k;
    int dist2=0;
    int max=0;

    visited[A] = true;

    for (k = 1; k <= V; ++k) {
        if(!visited[k]){
            dist2= length[A][k]+longestPath(k);
            if(dist2>max){
                max=dist2;
            }
        }
    }
    visited[A]=false;
    return(max);
}

Answer 1

Su relación de recurrencia es T(n, m) = mT(n, m-1) + O(n), donde n denota el número de nodos y m denota el número de nodos no visitados (porque se llama a veces longestPath m, y hay un bucle que ejecuta los tiempos n prueba visitados). El caso base es T(n, 0) = O(n) (sólo la prueba visitado).

Resolver esto y yo creo que se obtiene T (n, n) es O (n * n!).

Editar

Trabajo:

T(n, n) = nT(n, n-1) + O(n) 
        = n((n-1)T(n, n-2) + O(n)) + O(n) = ...
        = n(n-1)...1T(n, 0) + O(n)(1 + n + n(n-1) + ... + n(n-1)...2)
        = O(n)(1 + n + n(n-1) + ... + n!)
        = O(n)O(n!) (see http://oeis.org/A000522)
        = O(n*n!)