Сегодня в классе мой учитель написал на доске этот рекурсивный факториальный алгоритм:

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

Она сказала, что это имеет стоимостьT(n-1) + 1.

Затем с помощью итерационного метода она сказала, чтоT(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, поэтому алгоритм останавливается, когдаn - j = 1, такj = n - 1.

После этого она заменилаj вT(n-1) + 1и получилT(1) + n-1.

Она прямо сказала, что для этого n-1 = 2$9Затем с помощью итерационного метода она сказала, что10$, поэтому стоимость алгоритма является экспоненциальной.

Я действительно потерял два последних шага. Может кто-нибудь объяснить мне их?