Complejidad computacional de un algoritmo de ruta más larga con un método recursivo

Question

Escribí un segmento de código para determinar la ruta más larga en un gráfico. A continuación está el código. Pero no sé cómo obtener la complejidad computacional en él debido al método recursivo en el medio. Como encontrar el camino más largo es un problema completo de NP, supongo que es algo así como O(n!) o O(2^n), pero ¿cómo puedo determinarlo?

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 longestPathm veces, y hay un bucle que se ejecuta la prueba visitado n veces). El caso base es T(n, 0) = O(n) (solo la prueba visitada).

Resuelve esto y creo que obtienes T (n, n) es O (n * n!).

EDITAR

de 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!)