Complexité de l'algorithme récursif factoriel

Aujourd'hui dans la classe de mon professeur a écrit sur le tableau noir de cette factorielle récursive de l'algorithme:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

Elle a dit qu'elle a un coût de T(n-1) + 1.

Puis à l'itération de la méthode, elle a dit que T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + jalors l'algorithme s'arrête lorsque n - j = 1donc j = n - 1.

Après cela, elle a substitué j dans T(n-1) + 1et obtenu T(1) + n-1.

Elle a déclaré que, pour que n-1 = 2(log2n-1)et donc le coût de l'algorithme est exponentielle.

J'ai vraiment perdu les deux dernières étapes. Pouvez s'il vous plaît quelqu'un m'expliquer à moi?

source d'informationauteur Francesco Bonizzi