Heute in der Klasse schrieb mein Lehrer diesen rekursiven Fakultätsalgorithmus an die Tafel:

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

Sie sagte, dass es Kosten von hatT(n-1) + 1.

Dann sagte sie das mit IterationsmethodeT(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + jDer Algorithmus stoppt also, wennn - j = 1, soj = n - 1.

Danach ersetzte siej imT(n-1) + 1und erhaltenT(1) + n-1.

Sie sagte das direkt für das n-1 = 2(Log2n-1)Die Kosten des Algorithmus sind also exponentiell.

Ich habe die letzten beiden Schritte wirklich verloren. Kann mir das bitte jemand erklären?